A New Modified Cholesky Factorization
Abstract
The modified Cholesky factorization of Gill and Murray plays and important role in optimization algorithms. Given a symmetric but not necessarily positive matrix A, it computes a Cholesky factorization of A+E, where E=O 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- square operations more than the standard Cholesky factorization. We present a new algorithm that has these same properties, but for which the theoretical bound on //E// is substantially smaller. 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 may prove useful in optimization algorithms.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 30, 1988
- Accession Number
- ADA205174
Entities
People
- Elizabeth Eskow
- Robert B. Schnabel
Organizations
- University of Colorado Boulder