SOFTWARE FOR A NEW MODIFIED CHOLESKY FACTORIZATION

This paper describes the software for a new modified Cholesky factorization recently proposed by the authors. Given a symmetric but not necessarily positive definite matrix A, the modified Cholesky factorization 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 modified Cholesky factorization was introduced by Gill and Murray and refined by Gill, Murray and Wright, and is commonly used in optimization algorithms. Our version, which is based upon new techniques, has a considerably smaller a priori upper bound on the size of E than the Gill, Murray and Wright factorization, and generally appears to produce a smaller E, and a well-conditioned A + E, in practice. Its cost, like the Gill, Murray and Wright version, is only a small multiple of n2 operations greater than the standard Cholesky factorization. Thus it may be useful in optimization algorithms. We summarize our algorithm and describe the code and its use.