Chordal graphs in triangular decomposition in top-down style
From MaRDI portal
Publication:2200301
DOI10.1016/J.JSC.2019.10.011zbMATH Open1443.05132arXiv1811.11023OpenAlexW2980517378MaRDI QIDQ2200301FDOQ2200301
Authors: Chenqi Mou, Yang Bai, Jiahua Lai 
Publication date: 19 September 2020
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Abstract: In this paper, we first prove that when the associated graph of a polynomial set is chordal, a particular triangular set computed by a general algorithm in top-down style for computing the triangular decomposition of this polynomial set has an associated graph as a subgraph of this chordal graph. Then for Wang's method and a subresultant-based algorithm for triangular decomposition in top-down style and for a subresultant-based algorithm for regular decomposition in top-down style, we prove that all the polynomial sets appearing in the process of triangular decomposition with any of these algorithms have associated graphs as subgraphs of this chordal graph. These theoretical results can be viewed as non-trivial polynomial generalization of existing ones for sparse Gaussian elimination, inspired by which we further propose an algorithm for sparse triangular decomposition in top-down style by making use of the chordal structure of the polynomial set. The effectiveness of the proposed algorithm for triangular decomposition, when the polynomial set is chordal and sparse with respect to the variables, is demonstrated by preliminary experimental results.
Full work available at URL: https://arxiv.org/abs/1811.11023
Recommendations
- On the chordality of polynomial sets in triangular decomposition in top-down style
- Analyses and implementations of chordality-preserving top-down algorithms for triangular decomposition
- Chordality preserving incremental triangular decomposition and its implementation
- Algorithms for computing triangular decompositions of polynomial systems
- Algorithms for computing triangular decomposition of polynomial systems
Symbolic computation and algebraic computation (68W30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph representations (geometric and intersection representations, etc.) (05C62) Solving polynomial systems; resultants (13P15)
Cites Work
- Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
- Title not available (Why is that?)
- A new efficient algorithm for computing Gröbner bases \((F_4)\)
- An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
- Complexity of Finding Embeddings in a k-Tree
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Triangulated graphs and the elimination process
- Sparse Gröbner bases: the unmixed case
- Advances in Cryptology - CRYPTO 2003
- Algorithmic Aspects of Vertex Elimination on Graphs
- Elimination methods
- A generalized Euclidean algorithm for computing triangular representations of algebraic varieties
- Decomposing polynomial systems into simple systems
- On the theories of triangular sets
- Title not available (Why is that?)
- The Use of Linear Graphs in Gauss Elimination
- Computing triangular systems and regular systems
- Decomposing polynomial sets into simple sets over finite fields: the zero-dimensional case
- A facial reduction algorithm for finding sparse SOS representations
- Mechanical theorem proving in geometries. Basic principles. Transl. from the Chinese by Xiaofan Jin and Dongming Wang
- A characterisation of rigid circuit graphs
- An elimination method for polynomial systems
- Triangular sets for solving polynomial systems: a comparative implementation of four methods
- Title not available (Why is that?)
- Algorithms for computing triangular decomposition of polynomial systems
- Characteristic set algorithms for equation solving in finite fields
- A characteristic set method for solving Boolean equations and applications in cryptanalysis of stream ciphers
- Algorithmic Thomas decomposition of algebraic and differential systems
- Decomposing polynomial sets into simple sets over finite fields: the positive-dimensional case
- Sparse FGLM algorithms
- A new algorithmic scheme for computing characteristic sets
- Attacking Bivium and Trivium with the characteristic set method
- Lagrangian constraints and differential Thomas decomposition
- Predicting Structure in Sparse Matrix Computations
- On the chordality of polynomial sets in triangular decomposition in top-down style
- Towards Mixed Gröbner Basis Algorithms
- Chordal networks of polynomial ideals
Cited In (9)
- Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure
- On the chordality of polynomial sets in triangular decomposition in top-down style
- Chordality preserving incremental triangular decomposition and its implementation
- Analyses and implementations of chordality-preserving top-down algorithms for triangular decomposition
- On the Chordality of Simple Decomposition in Top-Down Style
- Analyzing the dual space of the saturated ideal of a regular set and the local multiplicities of its zeros
- Exploiting variable sparsity in computing equilibria of biological dynamical systems by triangular decomposition
- Choosing the variable ordering for cylindrical algebraic decomposition via exploiting chordal structure
- Chordal networks of polynomial ideals
Uses Software
This page was built for publication: Chordal graphs in triangular decomposition in top-down style
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200301)
