most recent 30 from http://mathoverflow.net 2013-06-20T08:15:45Z http://mathoverflow.net/feeds/question/62904 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62904/complexity-of-eigenvalue-decomposition Majid 2011-04-25T09:57:42Z 2011-04-25T12:55:51Z

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

http://mathoverflow.net/questions/62904/complexity-of-eigenvalue-decomposition/62910#62910 unknown (google) 2011-04-25T10:58:31Z 2011-04-25T10:58:31Z

<p>Yep O(n^3) is right</p>

http://mathoverflow.net/questions/62904/complexity-of-eigenvalue-decomposition/62911#62911 Federico Poloni 2011-04-25T11:05:05Z 2011-04-25T11:05:05Z

<p>In practice, $O(n^3)$.</p> <p>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&lt;\omega&lt;2.376$. For this last assertion, see Demmel, Dimitriu, Holtz, "Fast linear algebra is stable". </p>

http://mathoverflow.net/questions/62904/complexity-of-eigenvalue-decomposition/62921#62921 ght 2011-04-25T12:55:51Z 2011-04-25T12:55:51Z

<p>Take a look at the following link (and references therein) for the complexity of various algorithms for common mathematical operations:</p> <p><a href="http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations" rel="nofollow">Computational Complexity of Mathematical Operations.</a></p> <p>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.</p>