math/kktdirect/pkg-descr

   1 KKTDirect implements an ordering method and accompanying factorization for
   2 the direct solution of saddle-point matrices (also known as KKT or equilibrium
   3 matrices).  A simple constraint on ordering together with an assumption on
   4 the rank of parts of the matrix are sufficient to guarantee the existence of
   5 the LDL^T factorization, stability concerns aside. In fact, D may be taken
   6 to be a diagonal matrix with +/-1 along the diagonal, and be fully determined
   7 prior to factorization, giving rise to a "signed Cholesky" factorization. A
   8 modified minimum-degree-like algorithm which incorporates this constraint is
   9 used, along with a simple algorithm to modify an existing fill-reducing
  10 ordering to respect the constraint. While a stability analysis is lacking,
  11 numerical experiments indicate that this is generally sufficient to avoid the
  12 need for numerical pivoting during factorization, with clear possible benefits
  13 for performance.
  14
  15 Note this is only alpha-quality proof-of-concept code: for example,
  16 out-of-memory errors are not handled gracefully, and the provided Minimum
  17 Degree routine is not yet competitive with other packages.
  18
  19 WWW: http://www.cs.ubc.ca/~rbridson/kktdirect/