Diagonalize Large Hermitian Matrices Efficiently?

[John943]

I am running a program that has to diagonalize large, complex Hermitian matrices (the largest they get is about 1000x1000). To diagonalize the matrix once isn't too bad, but I need to diagonalize thousands to millions of different Hermitian matrices each time I run a simulation. If I only need the eigenvalues of each matrix, is there an efficient method that does not require me to diagonalize each matrix to get said eigenvalues? I'm currently using a version of the QR algorithm to diagonalize the matrices but I was hoping there was a faster method. Is there a way to emulate the matrices with a series or polynomial of some sort? Any help is greatly appreciated (if anyone knows of any papers written on this topic that would be perfect). Thanks!

 

[Mandlebra]

There are methods using matrix multiplication and fixed points to pick out the largest eigenvalue if you only need that one. Is that the case here?

 

[John943]

That sounds helpful! I only ever need one eigenvalue from the computation (though not necessarily the largest); if you know of any resources on such methods could you point me to them? Hopefully I can adapt them to what I need. Thanks!

 

[Mandlebra]

Check out the power iteration method. The matrix must have a strictly largest ev, and this method will pick it out.

 

[AlephZero]

I wouldn't use your own code for the QR algorithm for this. Find the routine from a professional library like LAPACK (which is free) and use that. If you want to see the theory, google for the "LAPACK Working Notes" (that's a collection of 200+ papers many of which describ the research done to develop the methods - but you will need a strong background in linear algebra to understand some of them!)

That sounds helpful! I only ever need one eigenvalue from the computation (though not necessarily the largest); if you know of any resources on such methods could you point me to them? Hopefully I can adapt them to what I need. Thanks!

The obvious question is "how do you know which eigenvalue you want, if it's not the largest or the smallest, and you don't care about the eigenvectors"?

If you want an eigenvalue near some constant S, you can find the smallest (closest to 0) eigenvalues of (A - sI) using an interative method.