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!
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this communitySince 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!
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.