5
$\begingroup$

I am curious how to quickly compute the eigenvalues for arbitrary matrices, sparse or dense, restricted on some given interval of interest.

Suppose we have an arbitrary $n\times n$ matrix $A$, normally the complexity of the computing all the eigenvalues for $A$ is $O(n^3)$, I wonder if we could find an algorithm that does the same job while only bears an $O(n^2)$ or less complexity, or more specifically, the eigenvalues on an interval $(a,b)$. Is this possible at all?

For symmetric matrix, to my knowledge, we could use bisection method to somewhat get the job done, I would like to know if there are other tricks for general matrices as well.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ How large is your interval $(a,b)$? If you want an eigenvalue near a given point $\mu_0$, you can use the inverse power iteration. $\endgroup$ – Hui Zhang Mar 1 '12 at 17:30
  • $\begingroup$ If your matrix is general, it will have complex eigenvalues. What then is the meaning of finding the eigenvalues in $(a,b)$? $\endgroup$ – Arnold Neumaier Apr 14 '12 at 19:24
5
$\begingroup$

For a direct general result (as opposed to iterative approximation) you will have to compute the largest eigenvector first to find the smaller ones in the remaining orthonormal sub-space. Basically compute the largest eigenvector (mean projection of a unit-vector $O(N^2)$), and repeat in the remaining $N$-subspaces, subtracting previous projections against the matrix.

I think 'interval' is a somewhat poorly formed concept here. Basically if you compute the first eigenvector (and corresponding eigen-value), you may discover that its magnitude is below the desired window, in which case you hit your $N^2$ lower bound of computation. I think the upper interval bound $a$ will not matter, but the lower will decide what partition of the eigenvalues you must compute, hence leaving you somewhere between $N^2$ and $N^3$.

For sparse matrices checkout Arnoldi Iteration, and the corresponding math on Krylov subspaces/methods. These algorithms do a really good job at approximating the largest eigenvalues quickly, but sometimes grind a long time when the matrix has a poor condition number or other undesirable spectral properties.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

Inverse subspace iteration: http://en.wikipedia.org/wiki/Inverse_iteration is available in ARPACK.

Filter diagonalization: http://ab-initio.mit.edu/wiki/index.php/Harminv

Rayleigh-Chebyshev: ftp://ftp.math.ucla.edu/pub/camreport/cam10-05.pdf

Are designed for that problem. Inverse iteration is the standard approach.

Edit: I just noticed you're looking for possibly asymmetric eigenvalue problems. Filter diagonalization can still work but it's trickier. See www.cs.tsukuba.ac.jp/techreport/data/CS-TR-08-13.pdf

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Complexity - The inverse iteration algorithm requires solving a linear system or calculation of the inverse matrix. For non-structured matrices (not sparse, not Toeplitz,...) this requires $O(n^3)$ operations. $\endgroup$ – meawoppl Mar 1 '12 at 23:18
  • $\begingroup$ Please add more discussion of the methods to your answer, rather than just listing methods. $\endgroup$ – Geoff Oxberry Mar 1 '12 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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