Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

5 Answers 5

up vote 13 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.)

share|improve this answer
    
thanks! this is great. i should check MO more often! –  Lev Reyzin Nov 9 '10 at 12:57

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

share|improve this answer
    
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.

share|improve this answer
    
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.

share|improve this answer

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

share|improve this answer
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 posting your answer, you agree to the privacy policy and terms of service.

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