Abstract
Chordal graphs have deep roots in discrete optimization and also arise naturally in several areas of continuous optimization, including sparse matrix algorithms, positive semidefinite and Euclidean distance matrix completion, and the analysis of partial separability. In semidefinite optimization, properties of chordal graphs have been used in algorithms that exploit sparsity in the coefficients. Large semidefinite optimization problems often have coefficient matrices with a common, 'aggregate' sparsity pattern. The aggregate sparsity has important implications for the structure (sparsity and rank) of the solutions of the problem.
The talk will focus on applications of classical results in sparse matrix theory, and, in particular, the fact that for chordal sparsity patterns it is easy to compute zero-fill Cholesky factorizations, maximum-determinant and minimum-rank positive semidefinite completions, and minimum-dimension Euclidean distance matrix completions. These properties are very useful in theoretical analysis and in the development of algorithms (interior-point, first-order, and decomposition algorithms). Data structures and techniques from the sparse matrix literature, such as elimination trees, supernodal elimination trees, and multifrontal algorithms will play a unifying role in the derivation of the key results and algorithms.