## KKTDirect: a direct solver package for saddle-point ( KKT ) matrices

Robert Bridson

An ordering method and accompanying factorization for the direct solution of saddle-point
matrices (also known as KKT or equilibrium matrices) is presented. A simple constraint on ordering together with
an assumption on the rank of parts of the matrix are sufficient to
guarantee the existence of the LDL^T factorization, stability
concerns aside. In fact, D may be taken to be a diagonal matrix with +/-1 along
the diagonal, and be fully determined prior to factorization, giving rise to a
"signed Cholesky" factorization. A modified minimum-degree-like algorithm which incorporates
this constraint is demonstrated, along with a simple algorithm to modify an existing
fill-reducing ordering to respect the constraint. While a stability analysis is lacking,
numerical experiments indicate that this is generally sufficient to avoid
the need for numerical pivoting during factorization, with clear benefits
for performance possible. For example, a highly efficient Cholesky factorization
routine, based on separate symbolic and numerical phases and possibly
exploiting supernodes, can be easily adapted to this more general class of matrices.

Here is a preprint of the paper:
kktdirect.pdf. This used version 0.3 of the code for
numerical tests, which has since been improved.

Here is the code, released into the public domain:

- KKTDirect0.5.tar.gz,
an update to allow the use without external BLAS or LAPACK (though this is not recommended if
you have the choice). It also fixes a significant bug in symbolic factorization
which may appear sometimes on some platforms.
- KKTDirect0.4.tar.gz.
Version 0.4 significantly improves symbolic factorization for supernodal left-looking factorizations,
and fixes an infrequent bug in supernodal signed Cholesky factorization present in earlier versions.
- KKTDirect0.3.tar.gz, version 0.3

Please note this is only alpha-quality proof-of-concept code: for example,
out-of-memory errors are not handled gracefully, and the provided Minimum Degree routine
is not yet competitive with other packages. Use at your own risk.