1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Are you aware of caam.rice.edu/software/ARPACK , en.wikipedia.org/wiki/ARPACK and mathworks.com/help/matlab/ref/eigs.html ? $\endgroup$
    – Mark L. Stone
    Commented May 7, 2018 at 17:35
  • $\begingroup$ Nobody (in their right mind) actually constructs the matrix inverse when using inverse iteration. $\endgroup$
    – David Ketcheson
    Commented May 8, 2018 at 10:47
  • $\begingroup$ @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. $\endgroup$
    – haik
    Commented May 8, 2018 at 16:09
  • $\begingroup$ @DavidKetcheson Thanks, I just realized that. $\endgroup$
    – haik
    Commented May 8, 2018 at 16:10

1 Answer 1

Reset to default
4
$\begingroup$

This would get better answers at [scicomp.se], anyway:

  • if your matrix happens to be positive semidefinite, then after a suitable shift the smallest eigenvalues become the largest ones in modulus and can be computed with the power method. Similar tricks apply in cases when the sought eigenvalues are "at the border of the spectrum".
  • 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.
  • If the eigenvalues you are looking for are somewhere in the middle of the spectrum, in general you are going to need to solve shifted linear systems with your matrix inside the algorithm. There aren't many ways around this. Luckily, for "medium-large" matrices, this is feasible with sparse direct methods, and there are off-the-shelf libraries that do it for you taking care of the low-level details.
  • A recent family of algorithms that aims, among other things, to compute eigenvalues from inside the spectrum without the need to solve linear systems is the FEAST one. I have never used them personally, but I think they are worth exploring after Arnoldi if you determine that it does not meet your needs. Another algorithm aimed at larger-than-Arnoldi scale is called Jacobi-Davidson (JD).
Improve this answer
$\endgroup$
3
  • $\begingroup$ I really appreciate your detailed answer. The matrix to be processed is indeed positive semidefinite. Shift and invert should be useful when dealing with my problem. However, it seems that we need to have a good approximation to the eigenvalues and the eigenvalues are chosen in terms of their magnitude (absolute value) instead of algebraic values. Is that true? I need to take an in-depth study. $\endgroup$
    – haik
    Commented May 8, 2018 at 16:22
  • $\begingroup$ 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). $\endgroup$
    – Federico Poloni
    Commented May 8, 2018 at 18:14
  • $\begingroup$ Anyway, Arpack has an out-of-the-box "computational mode" to approximate the smallest (algebraically) eigenvalue of a matrix, so if your matrix is semidefinite then you're all set. $\endgroup$
    – Federico Poloni
    Commented May 8, 2018 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .