A revised modified Cholesky factorization algorithm

A modified Cholesky factorization algorithm introduced originally by Gill a nd Murray and refined by Gill, Murray, and Wright is used extensively in op timization algorithms. Since its introduction in 1990, a different modified Cholesky factorization of Schnabel and Eskow has also gained widespread us age. Compared with the Gill-Murray-Wright algorithm, the Schnabel-Eskow alg orithm has a smaller a priori bound on the perturbation, added to ensure po sitive definiteness, and some computational advantages, especially for larg e problems. Users of the Schnabel-Eskow algorithm, however, have reported c ases from two different contexts where it makes a far larger modification t o the original matrix than is necessary and than is made by the Gill-Murray -Wright method. This paper reports on a simple modification to the Schnabel -Eskow algorithm that appears to correct all the known computational diffic ulties with the method, without harming its theoretical properties or its c omputational behavior in any other cases. In new computational tests, the m odifications to the original matrix made by the new algorithm appear virtua lly always to be smaller than those made by the Gill-Murray-Wright algorith m, sometimes by significant amounts. The perturbed matrix is allowed to be more ill-conditioned with the new algorithm, but this seems to be appropria te in the known contexts where the underlying problem is ill-conditioned.