Sparse Matrix Decomposition and Completion with Chordal.jl
2021-07-28, 17:10–17:20 (UTC), JuMP Track

We will introduce Chordal.jl, which includes several extensible algorithms for sparse matrices with a chordal sparsity pattern. We will overview the algorithms in this package and showcase their application in sparse semidefinite programming.


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.

Theo Diamandis is a PhD student studying optimization at MIT.