what is the computational complexity of eigenvalue decomposition for a unitary matrix? is O(n^3) a correct answer?

1$\begingroup$ I have some doubts about the relevance of the answers given below. You cannot compute the eigenvalues of a general unitary matrix in finite time. Because, this calculations could be used to solve every polynomial equation with real roots (the real axis is transformed rationally into the unit circle). $\endgroup$ – Denis Serre Apr 25 '11 at 20:03

1$\begingroup$ Add "...up to a required approximation" to solve this issue. Otherwise you are right, one cannot compute them in any finite time with the usual set of operations. $\endgroup$ – Federico Poloni Jan 21 '14 at 22:44
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.
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.

2$\begingroup$ The current content of that link does not describe the complexity of eigenvalue decomposition, although its content is very good. $\endgroup$ – zhanxw Dec 6 '13 at 18:38
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 adhoc 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.

$\begingroup$ Please have a look at the paper: "The complexity of the matrix eigenproblem" by Victor Pan and Zhao Chen. Their Theorem 1 contradicts your claims... $\endgroup$ – Suvrit May 19 '15 at 21:58

$\begingroup$ @Suvrit is there some reason the unitary eigenvalue problem is not easier than the the general case? $\endgroup$ – Igor Rivin May 19 '15 at 23:54

1$\begingroup$ The OP was asking about unitary matrices. Note that if $U$ is unitary and $\omega=1$ with $\omega \notin \sigma(U)$, $i (U+\omega I)(U\omega I)^{1}$ is hermitian, so solving the unitary problem is essentially like solving the hermitian problem. $\endgroup$ – Robert Israel May 20 '15 at 0:53

$\begingroup$ Convergence of the unsymmetric QR algorithm is still an open problem. In the paper mentioned in my answer, the eigendecomposition is not computed using QR, but a completely different algorithm (inversefree doubling). $\endgroup$ – Federico Poloni May 20 '15 at 6:14

$\begingroup$ @Suvrit, the paper you referenced is interesting and I think it proves what it set out to prove, namely that one can compute eigenvalues in n^3 ops in a field, but it's not clear to me that the computational complexity is truly n^3 in floating point. I mean by that that for example, computing the gcd of a bunch of polynomials by the Euclidian algorithm could conceivably result in exponential growth of the coefficients. Am I right to be worried? $\endgroup$ – Sébastien Loisel May 20 '15 at 8:46