# Compute the eigenvectors corresponding to the $k$ smallest eigenvalues w.r.t high dimensional symmetric sparse matrix?

So far as I know:

1. The power iteration method can only get the eigenvector corresponding to the largest eigenvalue;
2. The inverse power iteration method requires that the matrix is invertible;
3. The QR algorithm requires too much storage space.

I'm not sure if I'm understanding the above points right.

Since the matrix is high dimensional, symmetric, and sparse, I was wondering if there is some efficient algorithm that can get the $k$ eigenvectors corresponding to the $k$ smallest eigenvalues.

It would be best not to perform the matrix inversion.

• – Mark L. Stone May 7 '18 at 17:35
• Nobody (in their right mind) actually constructs the matrix inverse when using inverse iteration. – David Ketcheson May 8 '18 at 10:47
• @MarkL.Stone Thank you very much. It seems that the eigs in matlab can solve this problem, which applies the Krylov-Schur Algorithm. And the lanczos method should also be useful. Since I need to implement the process myself, I should take an in-depth look at them. – haik May 8 '18 at 16:09
• @DavidKetcheson Thanks, I just realized that. – haik May 8 '18 at 16:10

• For all other cases, shifted Arnoldi (implemented in ARPACK which is suggested in the comments) is the go-to algorithm. It requires solving several linear systems with $A$, possibly shifted (i.e., $(A-tI)x=b$).
• If your matrix is singular, you can get by inverting $A-tI$ for a small $t$ rather than $A$, with similar results.
• What I was suggesting is shifting without inverting: apply Arnoldi, or the power method, to $tI-A$, where $t$ is larger than $\lambda_{\max}(A)$, and you should be set. Yes, the power method finds the largest eigenvalue in modulus, and so does Arnoldi (very roughly). – Federico Poloni May 8 '18 at 18:14