Complexity of Finding the Eigendecomposition of a Matrix

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

Here is a relatively recent answer that answers this (mostly) in the affirmative:

Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time

Where the complexity for a $\delta$ additive backwards error is $O(T_{MM}(n) \cdot \log^2(\frac{n}{delta})$, for finding a matrix V, and a diagonal matrix D such that $$||A-VDV^{-1}||<\delta$$ where $T_{MM}(n)$ is the time to stably compute a matrix product. There is also a talk by the authors that gives a good overview of the ideas behind the algorithm, and goes over the theoretical complexity of matrix diagonalization.

The algorithm uses some clever ideas in order to make a divide and conquer approach work, and exploits the fact that while the conditioning for eigendecomposition can be very poor, every matrix is close to some well conditioned problem (hence yielding backwards stability, a solution to a $\delta$ nearby problem).

I'm not an expert on the topic, but here is a brief explanation of the ideas in the paper. The term "pseudospectral shattering" comes from the desire for the pseudospectrum of a matrix to be separated into n distinct parts, so that every eigenvalue is "stably" separated (conditioning for the eigenvector problem depends on how close eigenvalues are, and the angle between eigenvectors, these two things also roughly govern the shape of the pseudospectra). Once the pseudospectrum is shattered, one can localize eigenvalues within each connected component of the pseudospectrum, and perform a sort of "2d bracketing" using a newton iteration to compute the matrix sign function (shift and bisect using sign function) to get eigenvalues, and then solve a linear system to get eigenvectors.

I believe that there's an issue in vergi's answer above in that the characteristic polynomial approach doesn't quite work (misleading in complexity) because you may need to store many many more bits in precision (as well as in intermediate steps) in order obtain the characteristic polynomial and find roots stably and accurately. There is some discussion in a talk by the authors in this paper about that issue in other eigendecomposition algorithms.

Answer 6

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.

Answer 7

See the intro of https://arxiv.org/abs/1912.08805 for a discussion of the literature around this problem. In short: O(n^3) has been known for symmetric matrices since the 60's, but was not known in general until recently.

Answer 8

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