A New Modified Cholesky Factorization
Citations Over TimeTop 10% of 1990 papers
Abstract
The modified Cholesky factorization of Gill and Murray plays an important role in optimization algorithms. Given a symmetric but not necessarily positive-definite matrix A, it computes a Cholesky factorization of $A + E$, where $E = 0$ if A is safely positive-definite, and E is a diagonal matrix chosen to make $A + E$ positive-definite otherwise. The factorization costs only a small multiple of $n^2 $ operations more than the standard Cholesky factorization. A new algorithm that has these same properties, but for which the theoretical bound on $||E||_\infty $ is substantially smaller, is presented. It is based upon two new techniques, the use of Gerschgorin bounds in selecting the elements of E, and a new way of monitoring positive definiteness. In extensive computational tests on indefinite matrices, the new factorization virtually always produces smaller values of $||E||_\infty $ than the existing method, without impairing the conditioning of $A + E$. In some cases the improvements are substantial. The new factorization has already been useful in optimization algorithms.
Related Papers
- → A New Modified Cholesky Factorization(1990)163 cited
- → CIMGS: An Incomplete Orthogonal FactorizationPreconditioner(1997)50 cited
- → The importance of structure in incomplete factorization preconditioners(2010)12 cited
- → Convergence analysis of accurate inverse Cholesky factorization(2013)3 cited
- Numerical Stability of Cholesky Factorization in Interior Point Methods for Linear Programming(1999)