Exploiting chordal structure in polynomial ideals: a Gröbner bases approach

DOI10.1137/151002666zbMATH Open1353.13033arXiv1411.1745OpenAlexW2295465424MaRDI QIDQ2818203FDOQ2818203

Diego Cifuentes, Pablo A. Parrilo

Publication date: 6 September 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Chordal structure and bounded treewidth allow for efficient computation in numerical linear algebra, graphical models, constraint satisfaction and many other areas. In this paper, we begin the study of how to exploit chordal structure in computational algebraic geometry, and in particular, for solving polynomial systems. The structure of a system of polynomial equations can be described in terms of a graph. By carefully exploiting the properties of this graph (in particular, its chordal completions), more efficient algorithms can be developed. To this end, we develop a new technique, which we refer to as chordal elimination, that relies on elimination theory and Gr"obner bases. By maintaining graph structure throughout the process, chordal elimination can outperform standard Gr"obner basis algorithms in many cases. The reason is that all computations are done on "smaller" rings, of size equal to the treewidth of the graph. In particular, for a restricted class of ideals, the computational complexity is linear in the number of variables. Chordal structure arises in many relevant applications. We demonstrate the suitability of our methods in examples from graph colorings, cryptography, sensor localization and differential equations.

Full work available at URL: https://arxiv.org/abs/1411.1745

zbMATH Keywords

treewidthchordal graphelimination theorystructured polynomialsGröbner bases

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cites Work

• A column approximate minimum degree ordering algorithm
• Polybori: A framework for Gröbner-basis computations with Boolean polynomials
• Schur products and matrix completions
• Cohen-Macaulay graphs
• Algorithmic graph theory and perfect graphs
• Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
• Complexity of Finding Embeddings in a k-Tree
• Solving multiple right hand sides linear equations
• Triangulated graphs and the elimination process
• Graph-coloring ideals: Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases
• Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases
• Sparse Gröbner bases
• On the Desirability of Acyclic Database Schemes
• Monomial Algebras
• A Polyhedral Method for Solving Sparse Polynomial Systems
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• The Use of Linear Graphs in Gauss Elimination
• Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
• Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity
• Efficient incremental algorithms for the sparse resultant and the mixed volume
• Binomial edge ideals and conditional independence statements
• Fast Software Encryption
• Algebraic characterization of uniquely vertex colorable graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

• Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure
• The m-Bézout bound and distance geometry
• Chordal
• Chordal Networks of Polynomial Ideals
• Chordal graphs in triangular decomposition in top-down style
• Using Gröbner bases for detecting polynomial identities: A case study on Fermat's ideal
• Choosing the variable ordering for cylindrical algebraic decomposition via exploiting chordal structure
• On the robust hardness of Gröbner basis computation
• The Structure of Polynomial Ideals and Gröbner Bases
• Exploiting sparsity for semi-algebraic set volume computation

Uses Software

• COLAMD
• PolyBoRi
• SageMath
• SINGULAR

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Gröbner bases and primary decomposition of polynomial ideals 👍 👎
• The Structure of Polynomial Ideals and Gröbner Bases 👍 👎
• Dimension-dependent bounds for Gröbner bases of polynomial ideals 👍 👎
• The Gröbner basis of the ideal of vanishing polynomials 👍 👎
• On generating sets and gröbner bases for polynomial ideals 👍 👎
• Gröbner basis for an ideal of a polynomial ring over an algebraic extension over a field and its applications 👍 👎
• Chordal Networks of Polynomial Ideals 👍 👎

This page was built for publication: Exploiting chordal structure in polynomial ideals: a Gröbner bases approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2818203)