6
$\begingroup$

I'm a bit confused by the vast amount of literature on solving eigenvalue problems. I have a sparse (large) matrix which I have already factored (by Cholesky or LDU). I would like to compute few eigenvectors of this matrix associated to the smallest eigenvalues. Is there any method that is : 1) efficient in terms of computation time 2) robust 3) could re-use the factorization of the original matrix ?

Thank you !

$\endgroup$
3
$\begingroup$

Use Arnoldi iteration on inv(A) and it should converge quickly to the smallest eigenpairs of A. ARPACK (and its reverse communication interface) would probably be the easiest route to flesh out working code quickly.

EDIT: Just to clarify, you don't actually compute inv(A), you just apply inv(A) to a vector x whenever ARPACK asks you to do a matvec (by applying L\D\U\x, for instance).

$\endgroup$
  • $\begingroup$ Thank you ! Yes of course, the factorization is best used that way :) $\endgroup$ – Tom Jun 10 '13 at 13:01
2
$\begingroup$

A rather straight forward method would be to use the Inverse Power Method with $\mu = 0$.

This method will converge to the eigenvalue of A with the smallest magnitude. One thing you want to be careful of is if the smallest eigenvalue isn't very close to 0 in magnitude, or you have several with the same magnitude, all of which are the minimum, you could end up with slow convergence or oscillations. Usually these shortcomings could be dealt with by changing $\mu$ every few iterations, however this would require refactoring the matrix. If its just slow convergence, and you don't want to refactor the matrix, you can just throw more iterations at it. If there are multiple eigenvalues with the same magnitude, you will have to change $\mu$ and refactor atleast once, which may or may not be worth it.

Luckily, trying this, even with your own implementation is a matter of a small handful of lines of code, so you can try it, see how it converges, and see if it will work in your case.

$\endgroup$
  • $\begingroup$ Thank you, but this only give the eigenvector associated to the smallest eigenvalue. Actually I want to compute few eigenvectors (say, between 5 and 200) on a large sparse symmetric matrix (more than 5000 unknowns)... I could possibly use deflation iteratively but it looks to be less efficient than block techniques... $\endgroup$ – Tom Jun 10 '13 at 12:40
  • $\begingroup$ Oh, okay. Yes you would be able to get the other ones, but that would likely require higher accuracy on the smallest eigenvalues, and an extra orthogonilizaiton step. It's doable, but as you said, a more direct method may be more efficient. $\endgroup$ – Godric Seer Jun 10 '13 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.