The complexity of cylindrical algebraic decomposition with respect to polynomial degree
From MaRDI portal
Publication:2829999
DOI10.1007/978-3-319-45641-6_12zbMATH Open1453.13079DBLPconf/casc/EnglandD16arXiv1605.02494OpenAlexW2370198512WikidataQ59590565 ScholiaQ59590565MaRDI QIDQ2829999FDOQ2829999
Authors: Matthew England, James H. Davenport 
Publication date: 9 November 2016
Published in: Computer Algebra in Scientific Computing (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1605.02494
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
Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Computer-aided design (modeling of curves and surfaces) (65D17) Solving polynomial systems; resultants (13P15)
Cites Work
- Partial cylindrical algebraic decomposition for quantifier elimination
- Computing cylindrical algebraic decomposition via triangular decomposition
- Title not available (Why is that?)
- Algorithms in real algebraic geometry
- 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
- Iterated discriminants
- Factors of iterated resultants and discriminants
- Explicit factors of some iterated resultants and discriminants
- Constructing fewer open cells by GCD computation in CAD projection
- Title not available (Why is that?)
- Improved projection for cylindrical algebraic decomposition
- Definability and fast quantifier elimination in algebraically closed fields
- The complexity of the word problems for commutative semigroups and polynomial ideals
- Real quantifier elimination is doubly exponential
- Title not available (Why is that?)
- Cylindrical algebraic decomposition using validated numerics
- On propagation of equational constraints in CAD-based quantifier elimination
- An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
- Le formalisme du résultant. (The formalism of resultant)
- Cylindrical Algebraic Decomposition I: The Basic Algorithm
- On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
- Algorithmic methods for investigating equilibria in epidemic modeling
- Optimising problem formulation for cylindrical algebraic decomposition
- MetiTarski: past and future
- Cylindrical algebraic decompositions for Boolean combinations
- Constructing a single open cell in a cylindrical algebraic decomposition
- Cylindrical algebraic sub-decompositions
- The complexity of quantifier elimination and cylindrical algebraic decomposition
- Truth table invariant cylindrical algebraic decomposition
- Dimension-dependent bounds for Gröbner bases of polynomial ideals
- Cylindrical algebraic decomposition using local projections
- Using the Regular Chains library to build cylindrical algebraic decompositions by projecting and lifting
- Improving the use of equational constraints in cylindrical algebraic decomposition
- Need polynomial systems be doubly-exponential?
- Truth table invariant cylindrical algebraic decomposition by regular chains
- Speeding up cylindrical algebraic decomposition by Gröbner bases
- Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition
- Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition
- Synthesis of optimal numerical algorithms using real quantifier elimination (case study: square root computation)
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
Uses Software
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)
