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.