Chordal networks of polynomial ideals
From MaRDI portal
Publication:5347294
DOI10.1137/16M106995XzbMATH Open1444.13037arXiv1604.02618OpenAlexW3099302898MaRDI QIDQ5347294FDOQ5347294
Authors: Diego Cifuentes, Pablo A. Parrilo 
Publication date: 23 May 2017
Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)
Abstract: We introduce a novel representation of structured polynomial ideals, which we refer to as chordal networks. The sparsity structure of a polynomial system is often described by a graph that captures the interactions among the variables. Chordal networks provide a computationally convenient decomposition into simpler (triangular) polynomial sets, while preserving the underlying graphical structure. We show that many interesting families of polynomial ideals admit compact chordal network representations (of size linear in the number of variables), even though the number of components is exponentially large. Chordal networks can be computed for arbitrary polynomial systems using a refinement of the chordal elimination algorithm from [Cifuentes-Parrilo-2016]. Furthermore, they can be effectively used to obtain several properties of the variety, such as its dimension, cardinality, and equidimensional components, as well as an efficient probabilistic test for radical ideal membership. We apply our methods to examples from algebraic statistics and vector addition systems; for these instances, algorithms based on chordal networks outperform existing techniques by orders of magnitude.
Full work available at URL: https://arxiv.org/abs/1604.02618
Recommendations
- Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
- Tools for computing primary decompositions and applications to ideals associated to Bayesian networks
- On the chordality of polynomial sets in triangular decomposition in top-down style
- Chordal graphs in triangular decomposition in top-down style
- scientific article; zbMATH DE number 1684384
Symbolic computation and algebraic computation (68W30) Computational aspects in algebraic geometry (14Q99) Solving polynomial systems; resultants (13P15)
Cites Work
- The RegularChains library in Maple 10
- Decompositions of binomial ideals
- Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
- The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
- Title not available (Why is that?)
- Complexity of Finding Embeddings in a k-Tree
- Branching Programs and Binary Decision Diagrams
- Solving zero-dimensional systems through the rational univariate representation
- Title not available (Why is that?)
- Algorithmic Aspects of Vertex Elimination on Graphs
- Monomial algebras
- Elimination methods
- A generalized Euclidean algorithm for computing triangular representations of algebraic varieties
- On the theories of triangular sets
- Modern computer algebra
- Binary Decision Diagrams
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Treewidth computations. I: Upper bounds
- Title not available (Why is that?)
- Computing triangular systems and regular systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Binomial edge ideals and conditional independence statements
- Solving zero-dimensional algebraic systems
- An efficient tree decomposition method for permanents and mixed discriminants
- Sparse polynomial division using a heap
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Commuting birth-and-death processes
Cited In (9)
- Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure
- Chordality preserving incremental triangular decomposition and its implementation
- Analyses and implementations of chordality-preserving top-down algorithms for triangular decomposition
- A geometric approach for analyzing parametric biological systems by exploiting block triangular structure
- On the Chordality of Simple Decomposition in Top-Down Style
- Title not available (Why is that?)
- Chordal graphs in triangular decomposition in top-down style
- Choosing the variable ordering for cylindrical algebraic decomposition via exploiting chordal structure
- Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
Uses Software
This page was built for publication: Chordal networks of polynomial ideals
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5347294)
