On the stability of the Cholesky factorization for symmetric quasi-definite systems

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 quasi-definite. The Cholesky factorization PKP' = LDL' is then known to exist for any permutation P, even though D is indefinite.

Quasi-definite 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 quasi-definite matrix is closely related to an unsymmetric positive-definite matrix, for which an LDM' factorization exists. Using Golub and Van Loan's analysis of the latter, conditions are derived under which Cholesky factorization is stable for quasi-definite systems. Some numerical results confirm the predictions.

Return To PEG's Home Page.