Prochain Exposé

Friday June 26th, 3PM Paris/France. (Webinar link)

Diego Cifuentes (MIT, Massachusetts, USA)

Graphical structure in polynomial systems: Chordal networks. (Slides)

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 particular, the notion of chordality and treewidth play a pivotal role in related areas such as numerical linear algebra, database theory, constraint satisfaction, and graphical models. Our main contribution is the introduction of a new representation of structured polynomial systems: “chordal networks”. Chordal networks provide a computationally convenient decomposition of the system into simpler (triangular) polynomial sets, while maintaining its underlying graphical structure. We illustrate through examples from different application domains that algorithms based on chordal networks can significantly outperform existing techniques.