complexity of eigenvalue decomposition what is the computational complexity of eigenvalue decomposition for a unitary matrix?
is O(n^3) a correct answer?
 A: 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".
EDIT: this is in the usual numerical linear algerbra model where the basic operations (+,-,*,/) are performed approximately in IEEE machine arithmetic and cost $O(1)$ each. If you consider multiple precision and variable complexities depending on the bit length of numbers, that is a completely different beast.
A: I think the other answers are wrong. I periodically look up this problem and I believe it to be open. I will summarize my opinion:


*

*The symmetric eigenvalue problems is "solved". Wilkinson was able to prove that the QR iteration, with his own special shift strategy, converges cubically. See this for example.

*The nonsymmetric eigenvalue problem is still open. The chapter on that subject in Golub and Van Loan says has a discussion on how the Wilkinson shift fails on some nonsymmetric matrices. They also mention that Wilkinson's ad-hoc shift should not be taken "too seriously" and that really it only gives the QR iteration a fresh start and a chance at better convergence.
As far as I can tell, nobody knows the computational complexity of the approximate eigenvalue problem.
Edit: I stand corrected. Thanks Suvrit.
A: 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.
A: Yep O(n^3) is right
