Suppose $A\in\mathbb{R}^{n\times n}$ is a symmetric, positive definite matrix. $A$ is big enough that it's expensive to solve $Ax=b$ directly.

Is there an iterative algorithm for finding the smallest eigenvalue of $A$ that doesn't involve inverting $A$ in each iteration?

That is, I'd have to use an iterative algorithm like conjugate gradients to solve $Ax=b$, so repeatedly applying $A^{-1}$ seems like an expensive "inner loop." I only need a single eigenvector.


  • 1
    $\begingroup$ Have you tried using the Cholesky decomposition? You'd have to factor $A$ into $L L^T$ with $L$ being a triangular matrix. Once you have the factorization (you only do this once) you can use it in every iteration to solve the system very fast by back and forward substitution. $\endgroup$ Commented Jan 2, 2016 at 21:54
  • $\begingroup$ Is A a sparse matrix? $\endgroup$ Commented Jan 2, 2016 at 21:55
  • $\begingroup$ $A$ has some block structure, but I'd prefer not to mess with it if I don't have to -- so I was looking into "matrix free methods." The "LOBPCG" algorithm has some promise, I think! @Juan, the Cholesky factorization is still quite expensive. $\endgroup$ Commented Jan 2, 2016 at 21:57
  • $\begingroup$ If you are using matlab or octave use the eigs-routine. It is an iterative method. There are options to specify which eigenvalue you want, e.g. smallest real. $\endgroup$ Commented Jan 3, 2016 at 12:17
  • $\begingroup$ I understand and am indeed using eigs in matlab. But if you specify options like "sm" in eigs, then it requires the inverse of $A$ rather than $A$. Check out the table in the documentation: mathworks.com/help/matlab/ref/eigs.html $\endgroup$ Commented Jan 3, 2016 at 16:35

1 Answer 1

  1. Compute the largest-magnitude eigenvalue $\lambda_{max}$ of $A$ (with, say, eigs('lm')).

  2. Then compute the largest magnitude (negative) eigenvalue $\hat{\lambda}_{max}$ of $M = A - \lambda_{max}I$ (again, through a standard call to eigs('lm')).

  3. Observe that $\hat{\lambda}_{max} + \lambda_{\max} = \lambda_{min}(A)$. The reason why this holds is explained here.

  4. Find your eigenvector $v$ by solving $(A - \lambda_{min} I) v = 0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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