A New Modified Cholesky Factorization

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² operations more than the standard Cholesky factorization. A new algorithm that has these same properties, but for which the theoretical bound on ||E||_∞ 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||_∞ 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.