-
Notifications
You must be signed in to change notification settings - Fork 38
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add support for complex Hermitian banded matrix eigenvalue problems #179
Comments
I realized after initially thinking of this issue that |
Looking at #101, it's because there's a complexity benefit. For an n x n symmetric banded matrix of bandwidth m, band reduction algorithms cost O(m n2) mathematically. That is, provided that one does not apply the O(m n2) required Givens rotations to a pre-allocated matrix for dense eigenvectors. Forming the dense eigenvectors is what LAPACK does, which costs O(n3) and is much more expensive in practice than a dense eigensolve. Once one has a symmetric tridiagonal problem, then the eigendecomposition of that also costs only O(n2). As for Hermitian problems, it's possible that the band reduction https://github.com/JuliaMatrices/BandedMatrices.jl/blob/310699438fd4f2c1089432f96e3f07b5fd47436d/src/symbanded/bandedeigen.jl#L188-L195 (and banded congruence for Hermitian-definite problems) is already implemented by multiple dispatch, though it would probably need to be checked against the Fortran reference. |
What do you mean when you say that the banded eigensolver is "much more expensive in practice than a dense eigensolve"? Also, does this apply if one is only interested in computing the eigenvalues (without eigenvectors)?
I was thinking this could be a possibility, but that would be very striking... |
I mean that dsbev.f is slow compared with dsyev.f (for any bandwidth). Have a look at the summary of #101 for more info. N.B. the name changes as part of the conversation ( |
We should add a comment to the code explaining why we do this so we don’t forget |
I was just scrolling through a diff comparison of chbtrd.f and dsbtrd.f and there are two meaningful-looking chunks that are in the former and not in the latter. Both of them have a similar form and look like this:
and replace something like this:
Other than that, there are some spots setting things to their real parts (I think?), some various I have never worked closely with Fortran code and the above looks rather confusing at first glance, though I am guessing I could figure it out with some Fortran syntax tutorials and a careful side-by-side read of the Julia and Fortran versions of |
There exists a generic implementation of |
A PR would be great! |
Will do! |
At the moment, it appears there is only support for eigenvalue problems for (real) symmetric banded matrices and not for complex Hermitian banded matrices.
It seems that the most direct route which mirrors the implementation for symmetric banded matrices is to implement tridiagonalization for complex Hermitian banded matrices. (In addition to
sbtrd!
, there should be a methodhbtrd!
which tridiagonalizes complex Hermitian banded matrices.)The text was updated successfully, but these errors were encountered: