Chordal Matrix Package—a library for chordal matrix computations

Chompack is a library for chordal matrix computations. It includes routines for:

  • symbolic factorization
  • numeric Cholesky factorization
  • forward and back substitution
  • maximum determinant positive definite completion
  • minimum rank completion
  • Euclidean distance matrix completion
  • computations with logarithmic barriers for sparse matrix cones
  • chordal conversion
  • computing a maximal chordal subgraph

The implementation is based on the supernodal-multifrontal algorithms described in these papers:

See also

L. Vandenberghe and M. S. Andersen, Chordal Graphs and Semidefinite Optimization, Foundations and Trends in Optimization, 2015. [doi | bib ]

M. S. Andersen, J. Dahl, and L. Vandenberghe, Logarithmic barriers for sparse matrix cones, Optimization Methods and Software, 2013. [doi | bib ]

Applications of these algorithms in optimization include sparse matrix cone programs, covariance selection, graphical models, and decomposition and relaxation methods.