# Is there an efficient $O(n^2)$ way to get the eigen decomposition given a LDL factorization?

Let's say I have a LDL factorization of a matrix A.

Is there an efficient $O(n^2)$ way to get the eigen decomposition of A given it's LDL factorization?

Is there a more efficient way, in case L and A are sparse and we have a fill-reducing permutation of A?

Thanks!

• It's unlikely. Most algorithms I can think of are $O(n^{3})$ in the dense case. If $L$ and $A$ are sparse, then the scaling probably changes to an expression in terms of the number of nonzeros. – Geoff Oxberry Jul 24 '15 at 0:18
• What about solving an optimization problem (or any other iterative procedure) and using the LDL as an initial guess? – Yuval Atzmon Jul 24 '15 at 8:57

It's unlikely. Demmel and co-authors have a paper called "Fast Linear Algebra is Stable" that shows that numerically stable algorithms for eigendecompositions (up to finite precision) cost at least as much as matrix multiplication, which is $O(n^{\omega})$, where $2 \leq \omega \leq 2.376$ (or so). Methods for transforming an LDL or Cholesky decomposition into an eigendecomposition typically use a polar decomposition (Newton methods for calculating this would be $O(n^{\omega})$) or other means of computing similar information (e.g., SVD, $O(n^{3})$).
I don't think sparsity helps that much here either. Iterative methods (Krylov subspace methods like Lanczos or Arnoldi) will be $O(n^{3})$ (that is, $O(n^{2})$ per eigenvalue). I don't know of any sparse direct methods for the polar decomposition. Sparse SVD exists, which will offer some savings over the dense algorithm, but I don't know that a result exists that states it will be $O(n^{2})$.
Optimization algorithms will use sparse Cholesky, LDL, or LU. The complexity of sparse Cholesky is $O(nnz(L))$, where $nnz$ is the number of nonzeros function, and for sparse LU, it is $\Omega(nnz(L) + nnz(U))$ and $O(n^{\omega})$. However, these algorithms will perform a factorization for each linear solve, which is at least once per iteration.