ON THE STABILITY OF CHOLESKY FACTORIZATION FOR SYMMETRIC QUASIDEFINITE SYSTEMS*

Abstract. Sparse linear equations Kd r are considered, where K is a specially structured symmetric indefinite matrix that arises in numerical optimization and elsewhere. Under certain conditions, K is quasidefinite. The Cholesky factorization PKPT LDLT is then known to exist for any permutation P, even though D is indefinite. Quasidefinite matrices have been used successfully by Vanderbei within barrier methods for linear and quadratic programming. An advantage is that for a sequence of K’s, P may be chosen once and for all to optimize the sparsity of L, as in the positive-definite case. A preliminary stability analysis is developed here. It is observed that a quasidefinite matrix is closely related to an unsymmetric positive-definite matrix, for which an LDMT factorization exists. Using the Golub and Van Loan analysis of the latter, conditions are derived under which Cholesky factorization is stable for quasidefinite systems. Some numerical results confirm the predictions. Key words, indefinite systems, symmetric quasidefinite (sqd) systems, unsymmetric positive-definite systems, backward stability, condition number, barrier methods, linear programming AMS subject classifications. 49D37, 65F05, 65K05, 90C3