In this talk, we will introduce chordal graphs and some of their core properties. These properties enable many otherwise difficult problems, such as minimum vertex coloring, to be solved efficiently. Furthermore, they lead to several decomposition results for sparse matrices.

We will introduce Chordal.jl, a package for working with sparse matrices that have a chordal sparsity pattern. We will overview the algorithms implemented in this package and their applications, including Euclidean distance matrix completion and optimization with sparse data.

We will conclude by using Chordal.jl to dramatically reduce the solve time of a sparse semidefinite program (SDP). Solving large, sparse semidefinite programs (SDPs) remains computationally prohibitive for many existing solvers, and this application largely motivated the development of this package.