Eigenvalue problem

Open discussion regarding features, bugs, issues, vendors, etc.

Eigenvalue problem

Postby yangtao » Fri Mar 10, 2006 10:55 am

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
yangtao
 
Posts: 5
Joined: Sun Feb 26, 2006 3:45 am

Postby Julien Langou » Fri Mar 10, 2006 11:18 am

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
Julien Langou
 
Posts: 733
Joined: Thu Dec 09, 2004 12:32 pm
Location: Denver, CO, USA

Postby yangtao » Fri Mar 10, 2006 11:09 pm

Thank you very much!
yangtao
 
Posts: 5
Joined: Sun Feb 26, 2006 3:45 am


Return to User Discussion

Who is online

Users browsing this forum: Bing [Bot], Yahoo [Bot] and 1 guest