Symmetric Quasi-Definite Matrices

Robert J. Vanderbei

DIMACS 93-72
Rutgers University
New Brunswick, NJ 08903

Abstract
We say that a symmetric matrix K is quasi-definite if it has the form
K =
"
?E AT
A F
#

where E and F are symmetric positive definite matrices. Although such matrices are indefinite, we show that any symmetric permutation of a quasi-definite matrix yields a factorization LDLT .

We apply this result to obtain a new approach for solving the symmetric indefinite systems arising in interior-point methods for linear and quadratic programming. These systems are typically solved either by reducing to a positive definite system or by performing a BunchParlett factorization of the full indefinite system at every iteration. Ours is an intermediate approach based on reducing to a quasi-definite system. This approach entails less fill-in than further reducing to a positive definite system but is based on a static ordering and is therefore more efficient than performing Bunch-Parlett factorizations of the original indefinite system.