Chordal graphs in triangular decomposition in top-down style
From MaRDI portal
Publication:2200301
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.
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
Cites work
- scientific article; zbMATH DE number 3970886 (Why is no real title available?)
- scientific article; zbMATH DE number 1206418 (Why is no real title available?)
- scientific article; zbMATH DE number 1263377 (Why is no real title available?)
- A characterisation of rigid circuit graphs
- A characteristic set method for solving Boolean equations and applications in cryptanalysis of stream ciphers
- A facial reduction algorithm for finding sparse SOS representations
- A generalized Euclidean algorithm for computing triangular representations of algebraic varieties
- A new algorithmic scheme for computing characteristic sets
- A new efficient algorithm for computing Gröbner bases \((F_4)\)
- Advances in Cryptology - CRYPTO 2003
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithmic Thomas decomposition of algebraic and differential systems
- Algorithms for computing triangular decomposition of polynomial systems
- An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
- An elimination method for polynomial systems
- Attacking Bivium and Trivium with the characteristic set method
- Characteristic set algorithms for equation solving in finite fields
- Chordal networks of polynomial ideals
- Complexity of Finding Embeddings in a k-Tree
- Computing triangular systems and regular systems
- Decomposing polynomial sets into simple sets over finite fields: the positive-dimensional case
- Decomposing polynomial sets into simple sets over finite fields: the zero-dimensional case
- Decomposing polynomial systems into simple systems
- Elimination methods
- Exploiting chordal structure in polynomial ideals: a Gröbner bases approach
- Lagrangian constraints and differential Thomas decomposition
- Mechanical theorem proving in geometries. Basic principles. Transl. from the Chinese by Xiaofan Jin and Dongming Wang
- On the chordality of polynomial sets in triangular decomposition in top-down style
- On the theories of triangular sets
- Predicting Structure in Sparse Matrix Computations
- Sparse FGLM algorithms
- Sparse Gröbner bases: the unmixed case
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- The Use of Linear Graphs in Gauss Elimination
- Towards Mixed Gröbner Basis Algorithms
- Triangular sets for solving polynomial systems: a comparative implementation of four methods
- Triangulated graphs and the elimination process
Cited in
(9)- Analyses and implementations of chordality-preserving top-down algorithms for triangular decomposition
- Chordal networks of polynomial ideals
- Exploiting variable sparsity in computing equilibria of biological dynamical systems by triangular decomposition
- Analyzing the dual space of the saturated ideal of a regular set and the local multiplicities of its zeros
- On the chordality of polynomial sets in triangular decomposition in top-down style
- On the Chordality of Simple Decomposition in Top-Down Style
- Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure
- Chordality preserving incremental triangular decomposition and its implementation
- Choosing the variable ordering for cylindrical algebraic decomposition via exploiting chordal structure
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)
