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!
$\begingroup$
$\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
$\begingroup$
$\endgroup$
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.
answered Jul 17 '15 at 1:36
