# Is there an efficient $O(n^2)$ way to estimate in MATLAB a matrix condition number given its LDL decomposition?

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!

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

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.