KKTDirect: a direct solver package for saddle-point ( KKT ) matrices 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.
References in zbMATH (referenced in 1 article )
Showing result 1 of 1.
- Mattingley, Jacob; Boyd, Stephen: Automatic code generation for real-time convex optimization (2010)