Abstract
Techniques based on chordal structure and bounded treewidth have been extensively studied in linear algebra, graphical models, constraint satisfaction, database theory, and many other areas. It is natural then to analyze to what extent chordality might also help to solve systems of polynomial equations. To this end, we propose a new technique, which we refer to as chordal elimination, that relies in elimination theory and Gröbner bases. By maintaining the graphical structure of the input polynomial system in all computations, chordal elimination can outperform standard Gröbner basis algorithms in many cases. Besides the theoretical developments, in this talk we will illustrate the suitability of our methods in examples arising from graph colorings, cryptography, sensor localization and differential equations. Based on joint work with Diego Cifuentes (MIT).