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

Question

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!

Answer 1

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.