4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Geoff Oxberry Jul 24 '15 at 0:18
  • $\begingroup$ What about solving an optimization problem (or any other iterative procedure) and using the LDL as an initial guess? $\endgroup$ – Yuval Atzmon Jul 24 '15 at 8:57
3
$\begingroup$

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.

That exhausts all I can think of regarding algorithmic complexity on this topic. Quadratic complexity algorithms are unlikely in the dense case, and also probably unlikely in the sparse case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.