complexity of eigenvalue decomposition

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

-
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). –  Denis Serre Apr 25 '11 at 20:03
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. –  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.

-
The current content of that link does not describe the complexity of eigenvalue decomposition, although its content is very good. –  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 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.

-
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... –  Suvrit May 19 at 21:58
@Suvrit is there some reason the unitary eigenvalue problem is not easier than the the general case? –  Igor Rivin May 19 at 23:54
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. –  Robert Israel May 20 at 0:53
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 (inverse-free doubling). –  Federico Poloni May 20 at 6:14
@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? –  Sébastien Loisel May 20 at 8:46

Yep O(n^3) is right

-