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.
Best Answer
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<<n$ or computing non-exact eigendecomposition for example by recursive PCA or online PCA.