most recent 30 from http://mathoverflow.net 2013-06-18T21:10:51Z http://mathoverflow.net/feeds/question/68778 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/68778/complexity-of-evd Yerriswamy 2011-06-25T05:20:07Z 2011-06-26T18:33:49Z

<p>What is the computational complexity of Eigen Value decomposition of a correlation matrix?</p>

http://mathoverflow.net/questions/68778/complexity-of-evd/68800#68800 Brian Borchers 2011-06-25T17:13:12Z 2011-06-25T17:13:12Z

<p>In practice using algorithms in EISPACK or LAPACK on floating point single or double precision symmetric matrices, computing the EVD takes $O(n^3)$ time. The constant hidden within the big $O$ is considerably larger than for Cholesky factorization. </p> <p>In theory (but such algorithms are not practically useful for typical double precision floating point computations on matrices with dimensions in the thousands to 10's of thousands), you can do as well as matrix multiplication, for which the best current complexity is if I recall correctly $O(n^{2.376})$. </p>

http://mathoverflow.net/questions/68778/complexity-of-evd/68867#68867 Igor Rivin 2011-06-26T18:33:49Z 2011-06-26T18:33:49Z

<p>See</p> <p><a href="http://cstheory.stackexchange.com/questions/2611/complexity-of-finding-the-eigendecomposition-of-a-matrix" rel="nofollow">http://cstheory.stackexchange.com/questions/2611/complexity-of-finding-the-eigendecomposition-of-a-matrix</a></p>