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:
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.