Eigenvalue problem

[yangtao]

Hi,

In lapack library, there are many routines for computing eigenvalues. But now, I only want to konw the maximum and the minimum eigenvalues for a real symmetric, positive definite matrix, because In my program, I will compute the maximum and the minimum eigenvalues for many, many times. So, the time saving become a serious problem.
Many routines will need N^3 operations. So can you tell me whether the routines for this problem needed less operations are contained in lapack library?
Thank you!

Yang

[Julien Langou]

Many routines will need N^3 operations. So can you tell me whether the routines for this problem needed less operations are contained in lapack library?

Yes all the symmetric eigenvalue routines in LAPACK will require O(N^3) operations. No way to work around this O(N^3) cost since the first step in all our solver is to reduce the symmetric dense matrix to tridiagonal form which cost ~4/3N^3.

Then in the tridiagonal solver some methods (dsyevx,dsyevd,dsyevr) can exploit efficiently the fact that you only want a few of the eigenvalues.

If you really want an O(n^2) cost to find the maximum and the minimum eigenvalues fo a dense symmetric matrix, I suggest you go with some iterative methods. This is a fairly easy problem for those methods and they should converge pretty fast. For example you can use as a first try ARPACK, LOBPCG, TRLAN or PRIMME.

All you need to provide for those packages is a matrix-vector product. Your problem is fairly easy so all those methods should work almost the same. Pick the one with the easier interface for you:).

Julien

[yangtao]

Thank you very much!