Computing and Mathematical Sciences Colloquium

Monday November 7, 2016 4:00 PM

Graph Structure in Polynomial Systems: Chordal Networks

Speaker: Professor Pablo Parrilo, Dept. of Electrical Engineering and Computer Science, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology
Location: Annenberg 105

The sparsity structure of a system of polynomial equations or an optimization problem can be naturally described by a graph summarizing the interactions among the decision variables. It is natural to wonder whether the structure of this graph might help in computational algebraic geometry tasks (e.g., in solving the system). In this lecture we will provide a gentle introduction to this area, focused on the key notions of chordality and treewidth, which are of great importance in related areas such as numerical linear algebra, database theory, constraint satisfaction, and graphical models. In particular, we will discuss "chordal networks", a novel representation of structured polynomial systems that provides a computationally convenient decomposition of a polynomial ideal into simpler (triangular) polynomial sets, while maintaining its underlying graphical structure. As we will illustrate through examples from different application domains, algorithms based on chordal networks can significantly outperform existing techniques. Based on joint work with Diego Cifuentes (MIT), preprint at https://arxiv.org/abs/1604.02618

Series Computing and Mathematical Sciences Colloquium Series

Contact: Carmen Nemer-Sirois at (626) 395-4561 carmens@cms.caltech.edu