Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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

4 Answers 4

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.

share|improve this answer

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.

share|improve this answer
1  
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.

share|improve this answer
    
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
1  
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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.