ON THE STABILITY OF CHOLESKY FACTORIZATION FOR SYMMETRICAL QUASIDEFINITE SYSTEMS

Sparse linear equations Kd = r are considered, where K is a specially structured symmetric indefinite matrix that arises in numerical optimi zation and elsewhere. Under certain conditions, K is quasidefinite. Th e Cholesky factorization PKPT = LDL(T) is then known to exist for any permutation P, even though D is indefinite. Quasidefinite matrices hav e been used successfully by Vanderbei within barrier methods for linea r 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 dev eloped here. It is observed that a quasidefinite matrix is closely rel ated to an unsymmetric positive-definite matrix, for which an LDM(T) f actorization exists. Using the Golub and Van Loan analysis of the latt er, conditions are derived under which Cholesky factorization is stabl e for quasidefinite systems. Some numerical results confirm the predic tions.