Chordal networks of polynomial ideals
From MaRDI portal
Publication:5347294
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.
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
Cites work
- scientific article; zbMATH DE number 554762 (Why is no real title available?)
- scientific article; zbMATH DE number 1182838 (Why is no real title available?)
- scientific article; zbMATH DE number 1979251 (Why is no real title available?)
- scientific article; zbMATH DE number 4121482 (Why is no real title available?)
- scientific article; zbMATH DE number 1827070 (Why is no real title available?)
- A generalized Euclidean algorithm for computing triangular representations of algebraic varieties
- Algorithmic Aspects of Vertex Elimination on Graphs
- An efficient tree decomposition method for permanents and mixed discriminants
- Binary Decision Diagrams
- Binomial edge ideals and conditional independence statements
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Branching Programs and Binary Decision Diagrams
- Commuting birth-and-death processes
- Complexity of Finding Embeddings in a k-Tree
- Computing triangular systems and regular systems
- Elimination methods
- Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
- Hilbert's Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility
- Modern computer algebra
- Monomial algebras
- On the theories of triangular sets
- Solving zero-dimensional algebraic systems
- Solving zero-dimensional systems through the rational univariate representation
- Sparse polynomial division using a heap
- The RegularChains library in Maple 10
- The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
- Treewidth computations. I: Upper bounds
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
- scientific article; zbMATH DE number 1684384 (Why is no real title available?)
- Chordal graphs in triangular decomposition in top-down style
- Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
- Choosing the variable ordering for cylindrical algebraic decomposition via exploiting chordal structure
Describes a project that uses
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)
