DIMACS TR: 93-72

Symmetric Quasi-Definite Matrices



Author: Robert J. Vanderbei

ABSTRACT

We say that a symmetric matrix $K$ is {\em quasi-definite} if it has the form K = \left[ \begin{array}{cc} -E & A^T \\ A & F \end{array} \right] \] where $E$ and $F$ are symmetric positive definite matrices. Although such matrices are indefinite, we show that {\em any} symmetric permutation of a quasi-definite matrix yields a factorization $LDL^{T}$.

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 Bunch-Parlett 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.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-72.ps

DIMACS Home Page