Welcome to MathOverflow

Question

2

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

flag	asked Apr 25 2011 at 9:57 Majid 21●2

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 2011 at 20:03

unknown (google) · Answer 1 · 2011-04-25 10:58:31Z UTC

0

Yep O(n^3) is right

answered Apr 25 2011 at 10:58

unknown (google)
1

Federico Poloni · Answer 2 · 2011-04-25 11:05:05Z UTC

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

ght · Answer 3 · 2011-04-25 12:55:51Z UTC

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.

complexity of eigenvalue decomposition

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.