what is the computational complexity of eigenvalue decomposition for a unitary matrix? is O(n^3) a correct answer?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In practice, $O(n^3)$. In theory, it has the same complexity of matrix multiplication and more or less all the "in practice $O(n^3)$" linear algebra problems, that is, $O(n^\omega)$ for some $2<\omega<2.376$. For this last assertion, see Demmel, Dimitriu, Holtz, "Fast linear algebra is stable". 


Take a look at the following link (and references therein) for the complexity of various algorithms for common mathematical operations: Computational Complexity of Mathematical Operations. In particular, the complexity of the eigenvalue decomposition for a unitary matrix is, as it was mentioned before, the complexity of matrix multiplication which is $O(n^{2.376})$ using the Coppersmith and Winograd algorithm. 


Yep O(n^3) is right 

