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.