<p>I know this is a really old question, but it seems like this recent paper <a href="https://arxiv.org/abs/1912.08805" rel="noreferrer">https://arxiv.org/abs/1912.08805</a> improves the runtime to <span class="math-container">$O(n^\omega)$</span>, down from <span class="math-container">$O(n^3)$</span>.</p>

CC BY-SA 4.0
2021-03-01T17:45:07.853Z
2021-03-01T17:45:07.853Z
walkerbacker
<p>This is a specialized version of a previous question:
    <a href="https://cstheory.stackexchange.com/questions/2611/complexity-of-finding-the-eigendecomposition-of-a-matrix">Complexity of Finding the Eigendecomposition of a Matrix</a> .</p>

<p>For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the eigen decomposition.  The question is: can we achieve sub-cubic complexity?  Thanks.</p>

CC BY-SA 2.5
2010-11-18T17:11:48.253Z
Does this really need a separate question? Surely if someone knew the answer to this special case they would have said so in the other question.
Warren Schudy
CC BY-SA 2.5
2010-11-18T17:55:54.037Z
I stressed worst-case in my question, so I think this is fair...
Lev Reyzin
CC BY-SA 2.5
2010-12-29T21:45:58.270Z
Are you sure about that O(N^3) time bound?  See my related question about Gaussian elimination.
Jeffε
CC BY-SA 2.5
2010-12-30T20:54:35.877Z
It seems from http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/24294#24294 you can get $O(n^3)$ for an *approximate* solution.
Lev Reyzin
<ds.algorithms><time-complexity><matrices><linear-algebra><na.numerical-analysis>
Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix
Lihong Li
# Complexity of Finding the Eigendecomposition of a *Symmetric* Matrix

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

This is a specialized version of a previous question:
[Complexity of Finding the Eigendecomposition of a Matrix](https://cstheory.stackexchange.com/questions/2611/complexity-of-finding-the-eigendecomposition-of-a-matrix) .

For NxN symmetric matrices, it is known that O(N^3) time suffices to compute the eigen decomposition. The question is: can we achieve sub-cubic complexity? Thanks.

**Tags:** ds.algorithms, time-complexity, matrices, linear-algebra, na.numerical-analysis

> **Comments:**
> **username_1**: Does this really need a separate question? Surely if someone knew the answer to this special case they would have said so in the other question.  
> **username_2**: I stressed worst-case in my question, so I think this is fair...  
> **username_3**: Are you sure about that O(N^3) time bound?  See my related question about Gaussian elimination.  
> **username_2**: It seems from http://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/24294#24294 you can get $O(n^3)$ for an *approximate* solution.  

---

## 1 answers

### Answer by username_4 on 2021-03-01. Score: 5

I know this is a really old question, but it seems like this recent paper <https://arxiv.org/abs/1912.08805> improves the runtime to $O(n^\omega)$, down from $O(n^3)$.


---

