A MODIFIED CHOLESKY ALGORITHM-BASED ON A SYMMETRICAL INDEFINITE FACTORIZATION

Given a symmetric and not necessarily positive definite matrix A, a mo dified Cholesky algorithm computes a Cholesky factorization P(A + E)P- T = R-T R, where P is a permutation matrix and E is a perturbation cho sen to make A + E positive definite. The aims include producing a smal l-normed E and making A+E reasonably well conditioned. Modified Choles ky factorizations are widely used in optimization. We propose a new mo dified Cholesky algorithm based on a symmetric indefinite factorizatio n computed using a new pivoting strategy of Ashcraft, Grimes, and Lewi s. We analyze the effectiveness of the algorithm, both in theory and p ractice, showing that the algorithm is competitive with the existing a lgorithms of Gill, Murray, and Wright and Schnabel and Eskow. Attracti ve features of the new algorithm include easy-to-interpret inequalitie s that explain the extent to which it satisfies its design goals, and the fact that it can be implemented in terms of existing software.