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 at 22:44
add comment

3 Answers

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".

share|improve this answer
add comment

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
    
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
add comment

Yep O(n^3) is right

share|improve this answer
add comment

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.