search

bonevbs / HssMatrices.jl

A Julia package for hierarchically semiseparable (HSS) matrices.
MIT License
21 stars 5 forks source link

Positive Definitness #18

Open clarazen opened 3 years ago

clarazen commented 3 years ago

Hello Boris,

Does the approximation of a kernel matrix with hss guarantee to preserve positive definiteness? If yes, how does it achieve that?

Thank you!

mvsoom commented 2 years ago

I would also like to know :)

bonevbs commented 2 years ago

Hi - sorry for the silence! Somehow, I overlooked this completely.

As it stands, there is no guarantee - unless I overlook something. A fundamental problem is that both compression algorithms decouple the block-diagonal part from the off-diagonal. Only the off-diagonal part is compressed and even if some properties are conserved on this part, there is no guarantee that the overall matrix remain positive definite.

That being said, the truncation of the off-diagonal part can be treated as a perturbation, whose error is bounded by the compression tolerance). This can help to bound the error in the eigenvalues which, depending on the size of the eigenvalues, might be sufficient for you to guarantee definiteness. (See Chapter 7.2.2, Eigenvalue Sensitivity, Golub and van Loan - Matrix Computations)

mvsoom commented 2 years ago

OK, thank you very much for your answer.

Since the block diagonal is conserved, I assume the rank of the matrix is expected to be conserved too?

bonevbs commented 2 years ago

No, imagine you have a matrix with all entries equal to one. If you set all the off-diagonal blocks to 0, your rank will have increased from one to something higher.