Modified Cholesky algorithms: a catalog with new approaches.

Given an n × n symmetric possibly indefinite matrix A, a modified Cholesky algorithm computes a factorization of the positive definite matrix A + E, where E is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much additional cost and to keep A + E well-conditioned and close to A. Gill, Murray and Wright introduced a stable algorithm, with a bound of || E||₂ = O( n ²). An algorithm of Schnabel and Eskow further guarantees || E||₂ = O( n). We present variants that also ensure || E||₂ = O( n). Moré and Sorensen and Cheng and Higham used the block LBL ^T factorization with blocks of order 1 or 2. Algorithms in this class have a worst-case cost O( n ³) higher than the standard Cholesky factorization. We present a new approach using a sandwiched LTL ^T - LBL ^T factorization, with T tridiagonal, that guarantees a modification cost of at most O( n ²). [ABSTRACT FROM AUTHOR]