6
$\begingroup$

I have a symmetric indefinite matrix, $H$. I also have a routine that can compute the algebraically smallest eigenvalues of a symmetric indefinite matrix. I would like to compute the eigenvalues with smallest magnitude using my existing code.

One way I can do this is to use my routine to compute the algebraically smallest eigenpairs of $H^2$. Then I can use Rayleigh quotients to figure the smallest magnitude eigenvalues of $H$. This works great but is very slow since $cond(H^2) = cond(H)^2$.

Is there a better way?

Improve this question
$\endgroup$
5
  • $\begingroup$ What does "algebraically smallest" mean? $\endgroup$
    – Dan
    Mar 29, 2012 at 20:08
  • $\begingroup$ from his way of currently solving it one can infer that it means "absolutely smallest" $\endgroup$
    – Arnold Neumaier
    Mar 29, 2012 at 20:13
  • $\begingroup$ By algebraically smaller I mean closer to $-\infty$. I don't know the proper term. $\endgroup$
    – dranxo
    Mar 29, 2012 at 22:21
  • $\begingroup$ What you say here is just termed ''smallest'' (in your case = most negative). You'd get this by running the Lanczos algorithm. But the smallest eigenvalue of H^2 gives you the eigenvalue closest to 0 (the absolutely smallest), not to -infty, so I inferred that you meant that. So what do you really mean? If the spectrum were 2,1,-2,-5, which eigenvalue should be returned? $\endgroup$
    – Arnold Neumaier
    Mar 30, 2012 at 7:43
  • $\begingroup$ The current code will return -5. I would like a way to get 1. $\endgroup$
    – dranxo
    Mar 30, 2012 at 18:05

2 Answers 2

Reset to default
5
$\begingroup$

If you can afford a single factorization of $H$ you can find the absolute largest eigenvalue of $H^{-1}$ by the Lanczos algorithm, using the factorization to calculate matrix-vector products with $H^{-1}$. The inverse then gives the absolutely smallest eigenvalue of $H$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, inverse iteration can do it. Problem is that the bare bones matrix library I'm using does not have a linear solver and it's nontrivial to code up a good one that can handle indefinite matrices. $\endgroup$
    – dranxo
    Mar 29, 2012 at 22:27
1
$\begingroup$

You can use Jacobi-Davidson to find the lowest eigenvalue(s). Also see this question for related issues.

Improve this answer
$\endgroup$

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.