Exploiting chordal structure in polynomials ideals: A Gröbner bases approach

Chordal structure and bounded treewidth allow for efficient computation in numerical linear algebra, graphical models, constraint satisfaction and many other areas. We begin the study of how to exploit chordal structure in computational algebraic geometry. Concretely, we develop a new technique for solving systems of polynomial equations, chordal elimination, that relies on elimination theory and Gröbner bases. By maintaining graph structure throughout the process, chordal elimination can outperform standard Gröbner basis algorithms in many cases. We show applications from graph colorings, cryptography, sensor localization and differential equations.

Download paper here

See also:

• My slides from CACAO Seminar, UC Davis’ 14
• Pablo’s presentation at the Simons Institute for the Theory of Computing’ 14
• Chordal package