Exploiting chordal structure in systems of polynomial equations

[摘要] Chordal structure and bounded treewidth allow for efficient computation in linear algebra, graphical models, constraint satisfaction and many other areas. Nevertheless, it has not been studied whether chordality might also help solve systems of polynomials. We propose a new technique, which we refer to as chordal elimination, that relies in elimination theory and Gröbner bases. Chordal elimination can be seen as a generalization of sparse linear algebra. Unlike the linear case, the elimination process may not be exact. Nonetheless, we show that our methods are well-behaved for a large family of problems. We also use chordal elimination to obtain a good sparse description of a structured system of polynomials. By maintaining the graph structure in all computations, chordal elimination can outperform standard Gröbner basis algorithms in many cases. In particular, its computational complexity is linear for a restricted class of ideals. Chordal structure arises in many relevant applications and we propose the first method that takes full advantage of it. We demonstrate the suitability of our methods in examples from graph colorings, cryptography, sensor localization and differential equations.

[发布机构] Massachusetts Institute of Technology