3
$\begingroup$

Since evaluating a matrix condition number usually takes $O(n^3)$, I wonder whether there is an efficient $O(n^2)$ way to estimate in MATLAB a matrix condition number given its LDL decomposition.

Thank you!

$\endgroup$
  • $\begingroup$ Does it have extra structure (symmetry, etc)? $\endgroup$ – Jesse Chan Jul 16 '15 at 19:45
  • 1
    $\begingroup$ Yes, it is positive definite (and therefore symmetric) $\endgroup$ – Yuval Atzmon Jul 16 '15 at 19:52
  • $\begingroup$ Oops, somehow missed the "LDL" part. $\endgroup$ – Jesse Chan Jul 16 '15 at 20:17
1
$\begingroup$

There should be. Given a factorized matrix (usually LU), there are iterative methods to estimate the norm of the matrix and its inverse, and thus estimate the condition number in $\mathcal{O}(n^{2})$ time. Since $DL^{T}$ is upper triangular, you could alter methods that usually use an iterative method with an LU factorization by supplying $D$ and $L^{T}$ separately (this might require some hacking of source code if the routine isn't available in, for instance, BLAS). Basically, since $U$ is only going to be used in matrix-vector products, you would instead take matrix-vector products of $L^{T}$ and $D$, which would still be $\mathcal{O}(n^{2})$. ALGLIB provides some helpful documentation to get you started.

$\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.