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

Published in SIAM J. Discrete Math., 2016

Recommended citation: Diego Cifuentes, Pablo Parrilo (2016). "Exploiting chordal structure in polynomials ideals: A Gröbner bases approach." SIAM J. Discrete Math.. 30(3):1534-1570. http://dx.doi.org/10.1137/151002666

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: