Graph Structure in Polynomial Systems: Chordal Networks [Math Dept.]

Topic: 
Graph Structure in Polynomial Systems: Chordal Networks
Tuesday, January 31, 2017 - 3:00pm
Venue: 
Math 380-C
Speaker: 
Pablo Parrilo (MIT)
Abstract / Description: 

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 talk we will provide an 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).