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 and optimization 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).
You are here
Pablo Parrilo, MITTitle: Graph Structure in Polynomial Systems: Chordal NetworksAbstract:Bio: Pablo A. Parrilo is the Joseph F. and Nancy P. Keithley Professor of Electrical Engineering and Computer Science at MIT, with a joint appointment in the Mathematics Department. He is affiliated with the Laboratory for Information and Decision Systems (LIDS) and the Operations Research Center (ORC). Past appointments include Assistant Professor at the Automatic Control Laboratory of the Swiss Federal Institute of Technology (ETH Zurich), and Visiting Associate Professor at the California Institute of Technology. He received an Electronics Engineering undergraduate degree from the University of Buenos Aires, and a PhD in Control and Dynamical Systems from the California Institute of Technology. His research interests include optimization, machine learning, control and identification, robustness analysis and synthesis, and the development and application of computational tools based on convex optimization and algorithmic algebra to practically relevant engineering problems. Prof. Parrilo has received several distinctions, including the Donald P. Eckman Award of the American Automatic Control Council, the SIAM Activity Group on Control and Systems Theory (SIAG/CST) Prize, the IEEE Antonio Ruberti Young Researcher Prize, and the Farkas Prize of the INFORMS Optimization Society. He is an IEEE and SIAM Fellow.