The sparsity structure of a system of polynomial equations or an optimisation problem can be naturally described by a graph summarising 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 tree-width, 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 the joint work with Diego Cifuentes (MIT).

Speaker Bio

Pablo A. Parrilo is a Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology, where 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), Visiting Associate Professor at the California Institute of Technology, as well as short-term research visits at the University of California at Santa Barbara (Physics), Lund Institute of Technology (Automatic Control), and University of California at Berkeley (Mathematics). 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 optimisation methods for engineering applications, control and identification of uncertain complex systems, robustness analysis and synthesis, and the development and application of computational tools based on convex optimisation and algorithmic algebra to practically relevant engineering problems. Professor Parrilo has received several distinctions, including a Finmeccanica Career Development Chair, 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.

For more information about the ESD Seminars Series, please contact Karthik Natarajan at karthik_natarajan@sutd.edu.sg.