Symmetric Quasi-Definite Matrices
Robert J. Vanderbei
New Brunswick, NJ 08903
We say that a symmetric matrix K is quasi-definite if it has the form
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.