Author tjdiamandis
22 Stars
Updated Last
1 Year Ago
Started In
February 2021


Dev Build Status codecov

NOTE: This package is very much a work in progress. Feature requests welcome!


This package implements data structures and subroutines for chordal matrices. It is largely a (work in progress) port of to Julia and currently includes routines for

  • Chordal Decomposition of PSD matrices
  • Maximum Determinant PSD completion
  • Chordality tests and perfect elimination ordering

These algorithms are (mostly) based on the multi-frontal algorithms described in Logarithmic Barriers for Sparse Matrix Cones and the survey paper Chordal Graphs and Semidefinite Optimization.

Additionally, Chordal.jl includes utility functions for the elimination tree and clique tree data structures described in these papers.

Chordal Decomposition

Chordal decomposition breaks up a large n x n PSD matrix constraint into K smaller n_k x n_k PSD constraints. These smaller constraints correspond to the cliques in the chordal graph associated with the aggregate sparsity pattern of the problem (i.e., the matrices associated with the constraints and objective function involving the PSD variable).

These cliques can be further combined (replacing structural zeros with numeric zeros) to optimize optimization algorithm performance. This package uses the clique graph-based merging scheme introduced by Garstka et al. in A clique graph based merging strategy for decomposable SDPs and implemented in COSMO.jl).

Additional functionality to include and TODOs

  • Min rank matrix completion
  • Utility functions for SDP decomposition with JuMP
  • Symbolic and numeric cholesky factorization
  • Allow user-specified weight function for clique graph merging
  • Euclidean distance matrix completion
  • Only support LMI form of SDP & use Dualization.jl to convert standard form.


See also

  • COSMO.jl is a conic solver that uses chordal decomposition for large PSD constraints.
  • includes the same algorithms in Python.