Kktdirect

Direct solver package for saddle-point (KKT) matrices

KKTDirect implements an ordering method and accompanying factorization for the direct solution of saddle-point matrices also known as KKT or equilibrium matrices. 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 used, 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 possible benefits for performance.

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.