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