# Most efficient algorithm to calculate eigenvalues and eigenvectors of symmetric positive definite matrix

Suppose I have a symmetric positive definite matrix and I want to calculate all its eigenvalues and eigenvectors (eigenvalue decomposition). What's the most efficient algorithm (e.g. lowest complexity) to find that?

I found this question that shows a algorithm to find in $$O(n^3 + (nlog^2 n) log b)$$ for any matrix, since it doesn't take into account the fact that a matrix is symmetric and positive definite I suppose there is a faster algorithm for this case. I also found this paper, that has a method called "QR method" that works for symmetric real valued matrix, but it also doesn't take into account the positive definite.

• en.wikipedia.org/wiki/LOBPCG this is the only method I've found seen that requires positive-definiteness. Nov 1, 2021 at 20:31

As far as I know, you cannot get lower than $$O(n^3)$$ for the full exact computation of the eigendecomposition. Mostly this is done per singular value decomposition. For methods and runtime in more detail I refer to Golub, G. H. and Van Loan, C. F. (2013). Matrix computations. Johns Hopkins Studies in the Mathematical Sciences page ~493. You can reduce complexity by only computing the first $$k$$ eigenvectors with $$k< or computing non-exact eigendecomposition for example by recursive PCA or online PCA.