Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
type: Item
instance of: scholarly article
zbMATH Open document ID: 1353.13033
DOI: 10.1137/151002666
author: Diego Cifuentes
author: Pablo A. Parrilo
published in: SIAM Journal on Discrete Mathematics
publication date: 2016-09-06T00:00:00Z
full work available at URL: https://arxiv.org/abs/1411.1745
Mathematics Subject Classification ID: 13P10
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 6624158
zbMATH Keywords: chordal graph
zbMATH Keywords: elimination theory
zbMATH Keywords: Gröbner bases
zbMATH Keywords: structured polynomials
zbMATH Keywords: treewidth
describes a project that uses: SageMath
describes a project that uses: SINGULAR
describes a project that uses: PolyBoRi
describes a project that uses: COLAMD
MaRDI profile type: Publication
OpenAlex ID: W2295465424
arXiv ID: 1411.1745
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: On the Desirability of Acyclic Database Schemes
cites work: Q4288578
cites work: Polybori: A framework for Gröbner-basis computations with Boolean polynomials
cites work: Fast Software Encryption
cites work: Q3077955
cites work: Q3413659
cites work: A column approximate minimum degree ordering algorithm
cites work: Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's Nullstellensatz
cites work: Graph-coloring ideals: Nullstellensatz certificates, Gröbner bases for chordal graphs, and hardness of Gröbner bases
cites work: Q4217791
cites work: Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
cites work: Efficient incremental algorithms for the sparse resultant and the mixed volume
cites work: Solving systems of polynomial equations with symmetries using SAGBI-Gröbner bases
cites work: Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity
cites work: Sparse Gröbner bases
cites work: Algorithmic graph theory and perfect graphs
cites work: Binomial edge ideals and conditional independence statements
cites work: Algebraic characterization of uniquely vertex colorable graphs
cites work: A Polyhedral Method for Solving Sparse Polynomial Systems
cites work: Q4734791
cites work: Q4356576
cites work: Q4789198
cites work: Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
cites work: The Use of Linear Graphs in Gauss Elimination
cites work: Schur products and matrix completions
cites work: Q4643890
cites work: Solving multiple right hand sides linear equations
cites work: Triangulated graphs and the elimination process
cites work: The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
cites work: Q4861423
cites work: Cohen-Macaulay graphs
cites work: Monomial Algebras
Recommended article: The Structure of Polynomial Ideals and Gröbner Bases
Recommended article: Q3714165
Recommended article: Gröbner bases and primary decomposition of polynomial ideals
Recommended article: On generating sets and gröbner bases for polynomial ideals
Recommended article: Q3568025
Recommended article: Chordal Networks of Polynomial Ideals
Recommended article: The Gröbner basis of the ideal of vanishing polynomials
Recommended article: Dimension-dependent bounds for Gröbner bases of polynomial ideals
Recommended article: Gröbner basis for an ideal of a polynomial ring over an algebraic extension over a field and its applications
title: Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
review text: The paper contains a new elimination method for polynomial systems. The method is well suitable for systems with many equations and many variables, but there are only few variables in each equation. The idea is to use classical elimination (by Gröbner bases) for carefully chosen subsets of equations and variables in an iterative way. Algorithm 2 computes upper and lower bounds for elimination ideals. Theorem 3 gives sufficient conditions for these bounds being exact; hence in these cases, Algorithm 2 computes the precision ideals. Algorithm 3 computes a description of the ideal which has properties sumilar to a lexicographical Gröbner basis. In case of zero dimension, it is easy to compute all solutions when such a description is known.
reviewed by: Josef Schicho
description: scientific article; zbMATH DE number 6624158