12
$\begingroup$

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.

Thanks!

Improve this question
$\endgroup$
6
  • 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$
    – Juan M. Bello-Rivas
    Commented Jan 2, 2016 at 21:54
  • $\begingroup$ Is A a sparse matrix? $\endgroup$
    – Tolga Birdal
    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$
    – Justin Solomon
    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$
    – sebastian_g
    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$
    – Justin Solomon
    Commented Jan 3, 2016 at 16:35

1 Answer 1

Reset to default
15
$\begingroup$

  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$.

Improve this answer
$\endgroup$
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.