<p>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".</p>

<p>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.</p>

<p>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.</p>

<p>Have a look at
<a href="http://en.wikipedia.org/wiki/List_of_numerical_analysis_topics#Eigenvalue_algorithms">http://en.wikipedia.org/wiki/List_of_numerical_analysis_topics#Eigenvalue_algorithms</a></p>

CC BY-SA 2.5
2010-11-03T02:34:31.917Z
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
CC BY-SA 2.5
2010-11-03T01:35:21.403Z
2010-11-03T01:35:21.403Z
Thomas Steinke
<p>I will only give a partial answer relating to the eigenvalues of a matrix.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Bareiss_algorithm">Bareiss's Algorithm</a>.  See Yap's book on on <a href="http://cs.nyu.edu/~yap/book/alge/ftpSite/">"Fundamentals of Algorithmic Algebra"</a>, specifically, <a href="http://cs.nyu.edu/~yap/book/alge/ftpSite/l10.ps.gz">Chap. 10, "Linear Systems"</a>.</p>

<p>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, <a href="http://cs.nyu.edu/~yap/book/alge/ftpSite/l6.ps.gz">Chap. 6 "Roots of Polynomials"</a> for details.  I forget the exact run time but its polynomial in the degree of the characteristic polynomial and digits of accuracy desired.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-03T20:57:11.673Z
interesting, but this seems even worse than n^3. do we know this is the best possible?
Lev Reyzin
CC BY-SA 2.5
2010-11-04T17:38:07.567Z
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
CC BY-SA 2.5
2010-11-05T14:45:16.447Z
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
CC BY-SA 2.5
2010-11-03T04:48:55.383Z
2010-11-03T04:48:55.383Z
user834
<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-02T19:25:52.030Z
2010-11-02T19:25:52.030Z
asterix
<p>Here is a relatively recent answer that answers this (mostly) in the affirmative:</p>
<p><a href="https://arxiv.org/abs/1912.08805" rel="nofollow noreferrer">Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time
</a></p>
<p>Where the complexity for a <span class="math-container">$\delta$</span> additive backwards error is <span class="math-container">$O(T_{MM}(n) \cdot \log^2(\frac{n}{delta})$</span>, for finding a matrix V, and a diagonal matrix D such that <span class="math-container">$$||A-VDV^{-1}||&lt;\delta$$</span> where <span class="math-container">$T_{MM}(n)$</span> 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.</p>
<p>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 <strong>close</strong> to some well conditioned problem (hence yielding <strong>backwards</strong> stability, a solution to a <span class="math-container">$\delta$</span> nearby problem).</p>
<p>I'm not an expert on the topic, but here is a brief explanation of the ideas in the paper. The term &quot;pseudospectral shattering&quot; comes from the desire for the pseudospectrum of a matrix to be separated into n distinct parts, so that every eigenvalue is &quot;stably&quot; 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 &quot;2d bracketing&quot; 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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-04-15T03:49:57.217Z
2023-04-15T20:36:59.217Z
2023-04-15T20:36:59.217Z
Alex
<p>See the intro of <a href="https://arxiv.org/abs/1912.08805" rel="nofollow noreferrer">https://arxiv.org/abs/1912.08805</a> 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.</p>

CC BY-SA 4.0
2020-11-17T21:13:30.513Z
2020-11-17T21:13:30.513Z
nikhil srivastava
<p>This is an old question but some important literature seems to have been missed.</p>

<p>There are algorithms for which we have stronger theoretical support. For example, there are iterations based on the matrix sign function, see for example <a href="https://arxiv.org/pdf/math/0612264.pdf" rel="nofollow noreferrer">"Fast Linear Algebra is Stable" by Demmel, Dumitriu and Holtz</a>. 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 $&gt;0$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2018-01-14T15:41:24.590Z
2018-01-14T15:47:01.730Z
2018-01-14T15:47:01.730Z
Sébastien Loisel
<p>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 <em>Polynomial and Matrix Computations</em> by Bini and Pan.</p>

<p>Here's another reference - <em>Fast Linear Algebra is Stable</em>
<a href="http://www.netlib.org/lapack/lawnspdf/lawn186.pdf" rel="nofollow">http://www.netlib.org/lapack/lawnspdf/lawn186.pdf</a></p>

CC BY-SA 2.5
2010-11-02T14:34:54.093Z
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
CC BY-SA 2.5
2010-11-02T14:24:33.687Z
2010-11-05T10:15:59.663Z
2010-11-05T10:15:59.663Z
Anonymous
<p>Ryan answered a similar question on mathoverflow. Here's the link: <a href="https://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/24294#24294">mathoverflow-answer</a></p>

<p>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}$.</p>

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

<p>(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.)</p>

CC BY-SA 2.5
2010-11-09T08:58:28.650Z
2010-11-09T08:58:28.650Z
2017-04-13T12:57:54.777Z
virgi
<p>My question is simple:</p>

<blockquote>
  <p>What is the worst-case running time of the best known algorithm for computing an <a href="http://mathworld.wolfram.com/EigenDecomposition.htmlBlockquoteBlockquote" rel="noreferrer">eigendecomposition</a> of an $n \times n$ matrix? </p>
</blockquote>

<p>Does eigendecomposition reduce to matrix multiplication or are the best known algorithms $O(n^3)$ (via <a href="http://en.wikipedia.org/wiki/Singular_value_decomposition" rel="noreferrer">SVD</a>) in the worst case ?</p>

<p>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.</p>

<p><strong>EDIT</strong>: 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)$?</p>

<p><strong>EDIT 2</strong>: See <a href="https://cstheory.stackexchange.com/questions/3115/complexity-of-finding-the-eigendecomposition-of-a-symmetric-matrix">this related question</a> on <em>symmetric matrices</em>.</p>

CC BY-SA 2.5
2010-11-01T13:54:20.417Z
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
CC BY-SA 2.5
2010-11-01T15:13:40.523Z
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
CC BY-SA 2.5
2010-11-01T15:17:34.027Z
Do you know if $O(n^3)$ is the best known algorithm for computing the SVD?
Robin Kothari
CC BY-SA 2.5
2010-11-01T15:23:20.433Z
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
CC BY-SA 2.5
2010-11-01T19:20:51.613Z
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
CC BY-SA 2.5
2010-11-01T19:28:52.113Z
Thanks for the idea.  Unfortunately I am not even sure that $O(\min(mn^2,m^2n))$ is the best you can do for SVD.  Or perhaps it is known the special case of $m = n$ allows for some improvement.  I'm hoping that this is a basic question for someone working in the right subfield.
Lev Reyzin
CC BY-SA 2.5
2010-11-01T21:56:14.777Z
This might be better answered by people doing numerical methods rather than theoretical computer scientists (although they don't use the same kind of time complexity analysis, and worry a lot more about condition number).
Peter Shor 
CC BY-SA 2.5
2010-11-01T22:04:32.177Z
For sparse or structured matrices you can do a lot better. Google "black box linear algebra".
S Huntsman
CC BY-SA 2.5
2010-11-01T22:10:18.697Z
@Peter Thanks - yes I want a worst-case analysis that doesn't have problem-dependent "constants," like condition number!  Seems like the complexity of matrix multiplication is in the realm of mainstream tcs, so I was hoping this is too :) @S. Huntsman I am unfortunately only interested in worst case.
Lev Reyzin
CC BY-SA 2.5
2010-11-03T02:36:51.683Z
@Kaveh - we seem to be oscillating adding/removing the complexity theory tag.  Are you sure this question is a complexity theory question? I don't think any question about the best known algorithm immediately becomes a complexity theory question, despite the word appearing in the post's title.
Lev Reyzin
CC BY-SA 2.5
2010-11-03T05:42:03.937Z
@lev: sorry, i didn't notice we are oscillating. You are asking whether $O(n^3)$ is a lowerbound on the complexity of E.D., so this is a question on the complexity of a problem, doesn't this make it a [complexity](http://cstheory.stackexchange.com/tags/cc.complexity-theory/info) question?
Kaveh
CC BY-SA 2.5
2010-11-03T14:35:26.553Z
I am pretty sure n^3 isn't a known lower bound, as these are notoriously difficult to prove.  We pretty much don't have any lower bounds better than n^2 for matrix problems.  I was more asking what is the running time of the best algorithm to date.  Is that still a complexity question?  If not, should I change the title of my question?
Lev Reyzin
CC BY-SA 2.5
2010-11-03T14:44:14.263Z
Yeah, I would put the algorithms tag and remove the complexity-theory tag.
Robin Kothari
CC BY-SA 2.5
2010-11-03T18:48:15.470Z
@Robin,Lev: ds.algorithms seems better. :)
Kaveh
CC BY-SA 2.5
2011-02-09T17:02:05.910Z
Thanks for the interesting ideas and pointers above.  A related question is: for symmetric matrices, do we have more efficient algorithms for eigen-decomposition?  Thanks!
Lihong Li
<ds.algorithms><time-complexity><matrices><linear-algebra><na.numerical-analysis>
Complexity of Finding the Eigendecomposition of a Matrix
Lev Reyzin
# Complexity of Finding the Eigendecomposition of a Matrix

(Asked by: username_0 on 2010-11-01)

My question is simple:

> What is the worst-case running time of the best known algorithm for computing an [eigendecomposition](http://mathworld.wolfram.com/EigenDecomposition.htmlBlockquoteBlockquote) of an $n \times n$ matrix?

Does eigendecomposition reduce to matrix multiplication or are the best known algorithms $O(n^3)$ (via [SVD](http://en.wikipedia.org/wiki/Singular_value_decomposition)) 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](https://cstheory.stackexchange.com/questions/3115/complexity-of-finding-the-eigendecomposition-of-a-symmetric-matrix) on *symmetric matrices*.

**Tags:** ds.algorithms, time-complexity, matrices, linear-algebra, na.numerical-analysis
> **Comments:**
> **username_1**: 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.  
> **username_0**: Yes - they seem to extend to finding an LU-decomposition, but I don't know how to make it work for an eigen-decomposition.  
> **username_2**: Do you know if $O(n^3)$ is the best known algorithm for computing the SVD?  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: Thanks for the idea.  Unfortunately I am not even sure that $O(\min(mn^2,m^2n))$ is the best you can do for SVD.  Or perhaps it is known the special case of $m = n$ allows for some improvement.  I'm hoping that this is a basic question for someone working in the right subfield.  
> **username_3**: This might be better answered by people doing numerical methods rather than theoretical computer scientists (although they don't use the same kind of time complexity analysis, and worry a lot more about condition number).  
> **username_4**: For sparse or structured matrices you can do a lot better. Google "black box linear algebra".  
> **username_0**: @Peter Thanks - yes I want a worst-case analysis that doesn't have problem-dependent "constants," like condition number!  Seems like the complexity of matrix multiplication is in the realm of mainstream tcs, so I was hoping this is too :) @S. Huntsman I am unfortunately only interested in worst case.  
> **username_0**: @Kaveh - we seem to be oscillating adding/removing the complexity theory tag.  Are you sure this question is a complexity theory question? I don't think any question about the best known algorithm immediately becomes a complexity theory question, despite the word appearing in the post's title.  
> **username_5**: @lev: sorry, i didn't notice we are oscillating. You are asking whether $O(n^3)$ is a lowerbound on the complexity of E.D., so this is a question on the complexity of a problem, doesn't this make it a [complexity](http://cstheory.stackexchange.com/tags/cc.complexity-theory/info) question?  
> **username_0**: I am pretty sure n^3 isn't a known lower bound, as these are notoriously difficult to prove.  We pretty much don't have any lower bounds better than n^2 for matrix problems.  I was more asking what is the running time of the best algorithm to date.  Is that still a complexity question?  If not, should I change the title of my question?  
> **username_2**: Yeah, I would put the algorithms tag and remove the complexity-theory tag.  
> **username_5**: @Robin,Lev: ds.algorithms seems better. :)  
> **username_6**: Thanks for the interesting ideas and pointers above.  A related question is: for symmetric matrices, do we have more efficient algorithms for eigen-decomposition?  Thanks!  

---

## 8 answers

### Answer by username_14 on 2010-11-09. Score: 23 | Accepted answer

Ryan answered a similar question on mathoverflow. Here's the link: [mathoverflow-answer](https://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/24294#24294)

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 by username_7 on 2010-11-03. Score: 16

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>

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_8 on 2010-11-03. Score: 6

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](http://en.wikipedia.org/wiki/Bareiss_algorithm). See Yap's book on on ["Fundamentals of Algorithmic Algebra"](http://cs.nyu.edu/~yap/book/alge/ftpSite/), specifically, [Chap. 10, "Linear Systems"](http://cs.nyu.edu/~yap/book/alge/ftpSite/l10.ps.gz).

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"](http://cs.nyu.edu/~yap/book/alge/ftpSite/l6.ps.gz) 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.

> **Comments:**
> **username_0**: interesting, but this seems even worse than n^3. do we know this is the best possible?  
> **username_8**: 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.  
> **username_0**: So you're saying if I don't care about numerical stability issues, we can get it down to O(n^2.376)?  

---

### Answer by username_9 on 2010-11-02. Score: 5

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 by username_10 on 2023-04-15. Score: 2

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](https://arxiv.org/abs/1912.08805)

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 by username_11 on 2020-11-17. Score: 1

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 by username_12 on 2018-01-14. Score: 1

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](https://arxiv.org/pdf/math/0612264.pdf). 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 by username_13 on 2010-11-02. Score: 0

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>

> **Comments:**
> **username_0**: 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.  

---

