My question is simple:

What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix?

Does eigendecomposition reduce to matrix multiplication or are the best known algorithms $O(n^3)$ (via SVD) in the worst case ?

Please note that I am asking for a worst case analysis (only in terms of $n$), not for bounds with problem-dependent constants like condition number.

EDIT: Given some of the answers below, let me adjust the question: I'd be happy with an $\epsilon$-approximation. The approximation can be multiplicative, additive, entry-wise, or whatever reasonable definition you'd like. I am interested if there's a known algorithm that has better dependence on $n$ than something like $O(\mathrm{poly}(1/\epsilon)n^3)$?

EDIT 2: See this related question on symmetric matrices.

  • Have you looked at the reduction from matrix inversion to matrix multiplication in the CLRS algorithms textbook? I would start by looking at those ideas to see if they extend to eigen-decomposition. – Warren Schudy Nov 1 '10 at 13:54
  • Yes - they seem to extend to finding an LU-decomposition, but I don't know how to make it work for an eigen-decomposition. – Lev Reyzin Nov 1 '10 at 15:13
  • Do you know if $O(n^3)$ is the best known algorithm for computing the SVD? – Robin Kothari Nov 1 '10 at 15:17
  • 1
    As far as I know $O(\min(mn^2, m^2n))$ is the best known for SVD, but I am not sure. But eigen-decompositions seem less general, applying only to $n \times n$ matrices that satisfy a certain property, so it seems possible a better algorithm exists for that case. I am not at all an expert in this area, so I was hoping someone was aware of what the the state-of-the-art is for these things. – Lev Reyzin Nov 1 '10 at 15:23
  • Alright. I don't know much about this area either, but perhaps SVD computation can be reduced to eigendecomposition, since if you can eigendecompose AA* and A*A, you'll get the right and left matrices for the SVD. – Robin Kothari Nov 1 '10 at 19:20
up vote 17 down vote accepted

Ryan answered a similar question on mathoverflow. Here's the link: mathoverflow-answer

Basically, you can reduce eigenvalue computation to matrix multiplication by computing a symbolic determinant. This gives a running time of O($n^{\omega+1}m$) to get $m$ bits of the eigenvalues; the best currently known runtime is O($n^3+n^2\log^2 n\log b$) for an approximation within $2^{-b}$.

Ryan's reference is ``Victor Y. Pan, Zhao Q. Chen: The Complexity of the Matrix Eigenproblem. STOC 1999: 507-516''.

(I believe there is also a discussion about the relationship between the complexities of eigenvalues and matrix multiplication in the older Aho, Hopcroft and Ullman book ``The Design and Analysis of Computer Algorithms'', however, I don't have the book in front of me, and I can't give you the exact page number.)

Finding eigenvalues is inherently an iterative process: Finding eigenvalues is equivalent to finding the roots of a polynomial. Moreover, the Abel–Ruffini theorem states that, in general, you cannot express the roots of an arbitrary polynomial in a simple closed form (i.e. with radicals like the quadratic formula). Thus you cannot hope to compute eigenvalues "exactly".

This means that a spectral decomposition algorithm must be approximate. The running time of any general algorithm must depend on the desired accuracy; it can't just depend on the dimension.

I'm not an expert on this. I would guess that a cubic dependence on n is pretty good. The algorithms that I have seen all use matrix-vector multiplication, rather then matrix-matrix multiplication. So I would be somewhat surprised if it all boils down to matrix-matrix multiplication.

Have a look at http://en.wikipedia.org/wiki/List_of_numerical_analysis_topics#Eigenvalue_algorithms

  • Thanks for your answer - I will need some time to digest it! But if one uses matrix-vector multiplication, the dependence on n might perhaps be better than n^3. – Lev Reyzin Nov 3 '10 at 2:34

I will only give a partial answer relating to the eigenvalues of a matrix.

As previously mentioned, there are many iterative methods to find the eigenvalues of a matrix (e.g. power iteration), but in general, finding the eigenvalues reduces to finding the roots of the characteristic polynomial. Finding the characteristic polynomial can be done in $O(n^3 M_B[n(log n + L)] )$, where $M_B(s)$ is the cost of $s$ bit multiplies and $L$ is the bit size of the maximum entry, by a symbolic determinant calculation using Bareiss's Algorithm. See Yap's book on on "Fundamentals of Algorithmic Algebra", specifically, Chap. 10, "Linear Systems".

Once the characteristic polynomial is found, one can find the roots to any degree of accuracy desired by using isolating intervals. See Yap's book, Chap. 6 "Roots of Polynomials" for details. I forget the exact run time but its polynomial in the degree of the characteristic polynomial and digits of accuracy desired.

I suspect that calculating eigenvectors up to whatever degree of accuracy is also polynomial but I do not see a straight forward algorithm. There are, of course, the standard bag of tricks that have been previously mentioned, but as far as I know, none of them guarantee polynomial run time for a desired accuracy.

  • interesting, but this seems even worse than n^3. do we know this is the best possible? – Lev Reyzin Nov 3 '10 at 20:57
  • Run times on algorithms of this nature are tied to the complexity of Matrix Multiplication which is about O(n^3). I know about Strassen's algorithm but if you don't ignore numerical stability issues, then I believe you get back O(n^3) for matrix multiplication. Iterative methods might converge faster in the "average" case, but I believe, in general, about O(n^3) is the best you can do. – user834 Nov 4 '10 at 17:38
  • So you're saying if I don't care about numerical stability issues, we can get it down to O(n^2.376)? – Lev Reyzin Nov 5 '10 at 14:45

You could check out the new paper by Commandur and Kale which gives a combinatorial algorithm for Max-Cut. It seems (from a cursory reading) that their algorithm is based on combinatorially finding the eigenvector corresponding to the max eigenvalue, and then using Luca Trevisan's algorithm once they have this eigenvector.

It seems that they are using an alternative approach to Lanczos's algorithm for finding such an eigenvector, so it might be of interest. I'm not sure what is the claimed complexity of their method for finding the eigenvector, but it might be worth looking into. Also, since it is approximation ratio and not time per se that they are interested in, whatever time bounds they give might not be optimal.

This is an old question but some important literature seems to have been missed.

There are algorithms for which we have stronger theoretical support. For example, there are iterations based on the matrix sign function, see for example "Fast Linear Algebra is Stable" by Demmel, Dumitriu and Holtz. In that paper, it is shown that the eigenvalue problem can be solved in time $(O^{\omega+\eta})$, where $\omega$ is the exponent of matrix multiplication and $\eta$ is any number $>0$.

Yes, there is the Pan+Chen+Zheng paper that suggests assembling the characteristic polynomial and calculating in BigFloat because you lose a lot of bits of accuracy at the end, but not many people would consider this to be a practical approach.

I also mention that the most widely used algorithm, the Francis QR iteration, has no proof of convergence for general matrices; the book by Kressner discusses several counterexamples.

Yes, pretty much all of numerical linear algebra can be reduced to matrix multiplication, though, as always, numerical stability is an issue. Also, with problems such as eigendecomposition, you should be content with an approximation because the solution may be irrational. Check out the book Polynomial and Matrix Computations by Bini and Pan.

Here's another reference - Fast Linear Algebra is Stable http://www.netlib.org/lapack/lawnspdf/lawn186.pdf

  • 3
    Thanks for the pointer, but doing a search through the book on google books, I couldn't find the reduction to matrix multiplication. Do you have a pointer to some concrete reference or algorithm? And their SVD algorithms seem to depend on the condition number of the matrix, which is not a worst case analysis. Regarding numerical stability issues, etc., let's assume the idealized case, where all multiplications and divisions take unit time and produce exact answers. – Lev Reyzin Nov 2 '10 at 14:34

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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