The complexity of cylindrical algebraic decomposition with respect to polynomial degree
From MaRDI portal
Publication:2829999
Abstract: Cylindrical algebraic decomposition (CAD) is an important tool for working with polynomial systems, particularly quantifier elimination. However, it has complexity doubly exponential in the number of variables. The base algorithm can be improved by adapting to take advantage of any equational constraints (ECs): equations logically implied by the input. Intuitively, we expect the double exponent in the complexity to decrease by one for each EC. In ISSAC 2015 the present authors proved this for the factor in the complexity bound dependent on the number of polynomials in the input. However, the other term, that dependent on the degree of the input polynomials, remained unchanged. In the present paper the authors investigate how CAD in the presence of ECs could be further refined using the technology of Groebner Bases to move towards the intuitive bound for polynomial degree.
Recommendations
- Cylindrical algebraic decomposition with equational constraints
- Improving the use of equational constraints in cylindrical algebraic decomposition
- On using bi-equational constraints in CAD construction
- Cylindrical algebraic sub-decompositions
- Optimising problem formulation for cylindrical algebraic decomposition
Cites work
- scientific article; zbMATH DE number 1157648 (Why is no real title available?)
- scientific article; zbMATH DE number 1157658 (Why is no real title available?)
- scientific article; zbMATH DE number 2151220 (Why is no real title available?)
- Algorithmic methods for investigating equilibria in epidemic modeling
- Algorithms in real algebraic geometry
- An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
- Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
- Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
- Computing cylindrical algebraic decomposition via triangular decomposition
- Constructing a single open cell in a cylindrical algebraic decomposition
- Constructing fewer open cells by GCD computation in CAD projection
- Cylindrical Algebraic Decomposition I: The Basic Algorithm
- Cylindrical algebraic decomposition using local projections
- Cylindrical algebraic decomposition using validated numerics
- Cylindrical algebraic decompositions for Boolean combinations
- Cylindrical algebraic sub-decompositions
- Definability and fast quantifier elimination in algebraically closed fields
- Dimension-dependent bounds for Gröbner bases of polynomial ideals
- Explicit factors of some iterated resultants and discriminants
- Factors of iterated resultants and discriminants
- Improved projection for cylindrical algebraic decomposition
- Improving the use of equational constraints in cylindrical algebraic decomposition
- Iterated discriminants
- Le formalisme du résultant. (The formalism of resultant)
- MetiTarski: past and future
- Need polynomial systems be doubly-exponential?
- On propagation of equational constraints in CAD-based quantifier elimination
- On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
- Optimising problem formulation for cylindrical algebraic decomposition
- Partial cylindrical algebraic decomposition for quantifier elimination
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Real quantifier elimination is doubly exponential
- Speeding up cylindrical algebraic decomposition by Gröbner bases
- Synthesis of optimal numerical algorithms using real quantifier elimination (case study: square root computation)
- The complexity of quantifier elimination and cylindrical algebraic decomposition
- The complexity of the word problems for commutative semigroups and polynomial ideals
- Truth table invariant cylindrical algebraic decomposition
- Truth table invariant cylindrical algebraic decomposition by regular chains
- Using the Regular Chains library to build cylindrical algebraic decompositions by projecting and lifting
Cited in
(10)- Optimizing a particular real root of a polynomial by a special cylindrical algebraic decomposition
- Using machine learning to improve cylindrical algebraic decomposition
- Speeding up cylindrical algebraic decomposition by Gröbner bases
- Need polynomial systems be doubly-exponential?
- Cylindrical algebraic decomposition with equational constraints
- Deciding the consistency of non-linear real arithmetic constraints with a conflict driven search using cylindrical algebraic coverings
- Identifying the parametric occurrence of multiple steady states for some biological networks
- An approximate characterisation of the set of feasible trajectories for constrained flat systems
- Methodologies of Symbolic Computation
- Optimising problem formulation for cylindrical algebraic decomposition
This page was built for publication: The complexity of cylindrical algebraic decomposition with respect to polynomial degree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829999)
