# Complexity of EVD

What is the computational complexity of Eigen Value decomposition of a correlation matrix?

-
maybe google helps; also, on what model of computation? maybe the fact that your matrix is symmetric matters more than that it is a correlation matrix. –  Suvrit Jun 25 '11 at 5:30
And what is your motivation? –  András Bátkai Jun 26 '11 at 20:13

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.
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})$.
Thanks Brian; actually I had totally forgotten---the cs.SE answer links to a STOC paper that I had once skimmed. But indeed, it is not immediate to see that EVD complexity also boils down to matrix multiplication (in the $\epsilon$-accurate sense) –  Suvrit Jun 27 '11 at 3:03