Cylindrical algebraic sub-decompositions
From MaRDI portal
Publication:475412
DOI10.1007/S11786-014-0191-ZzbMATH Open1309.68232DBLPjournals/mics/WilsonBDE14arXiv1401.0647OpenAlexW3098379678WikidataQ59399761 ScholiaQ59399761MaRDI QIDQ475412FDOQ475412
Authors: Matthew England, David Wilson, Russell Bradford, James H. Davenport 
Publication date: 27 November 2014
Published in: Mathematics in Computer Science (Search for Journal in Brave)
Abstract: Cylindrical algebraic decompositions (CADs) are a key tool in real algebraic geometry, used primarily for eliminating quantifiers over the reals and studying semi-algebraic sets. In this paper we introduce cylindrical algebraic sub-decompositions (sub-CADs), which are subsets of CADs containing all the information needed to specify a solution for a given problem. We define two new types of sub-CAD: variety sub-CADs which are those cells in a CAD lying on a designated variety; and layered sub-CADs which have only those cells of dimension higher than a specified value. We present algorithms to produce these and describe how the two approaches may be combined with each other and the recent theory of truth-table invariant CAD. We give a complexity analysis showing that these techniques can offer substantial theoretical savings, which is supported by experimentation using an implementation in Maple.
Full work available at URL: https://arxiv.org/abs/1401.0647
Recommendations
computer algebrareal algebraic geometrysymbolic computationcomplexity analysiscylindrical algebraic decompositionMapleequational constraints
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Semialgebraic sets and related spaces (14P10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)
Cites Work
- QEPCAD B
- Partial cylindrical algebraic decomposition for quantifier elimination
- Solving systems of strict polynomial inequalities
- Computing cylindrical algebraic decomposition via triangular decomposition
- Title not available (Why is that?)
- Improved projection for cylindrical algebraic decomposition
- Real quantifier elimination is doubly exponential
- Computation with semialgebraic sets represented by cylindrical algebraic formulas
- 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
- Solving Polynomial Strict Inequalities Using Cylindrical Algebraic Decomposition
- Title not available (Why is that?)
- Cylindrical Algebraic Decomposition I: The Basic Algorithm
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- Algorithmic methods for investigating equilibria in epidemic modeling
- An incremental algorithm for computing cylindrical algebraic decompositions
- Optimising problem formulation for cylindrical algebraic decomposition
- Understanding branch cuts of expressions
- MetiTarski: past and future
- Cylindrical algebraic decompositions for Boolean combinations
- Constructing a single open cell in a cylindrical algebraic decomposition
- A :20piano movers' '
- Efficient projection orders for CAD
- Title not available (Why is that?)
- Geometry of branch cuts
- Solving polynomial systems over semialgebraic sets represented by cylindrical algebraic formulas
- On using bi-equational constraints in CAD construction
- The complexity of quantifier elimination and cylindrical algebraic decomposition
- Truth table invariant cylindrical algebraic decomposition
Cited In (22)
- On proving inequalities by cylindrical algebraic decomposition
- Using machine learning to improve cylindrical algebraic decomposition
- Need polynomial systems be doubly-exponential?
- Cylindrical algebraic decomposition with equational constraints
- On Approximations and Incidence in Cylindrical Algebraic Decompositions
- Deciding the consistency of non-linear real arithmetic constraints with a conflict driven search using cylindrical algebraic coverings
- Open non-uniform cylindrical algebraic decompositions
- Properness defects and projections and computation of at least one point in each connected component of a real algebraic set
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- Identifying the parametric occurrence of multiple steady states for some biological networks
- Constructing a single cell in cylindrical algebraic decomposition
- Cylindrical algebraic decomposition using validated numerics
- Solving polynomial systems over semialgebraic sets represented by cylindrical algebraic formulas
- An approximate characterisation of the set of feasible trajectories for constrained flat systems
- On delineability of varieties in CAD-based quantifier elimination with two equational constraints
- CAD and topology of semi-algebraic sets
- Computing cylindrical algebraic decomposition via triangular decomposition
- Truth table invariant cylindrical algebraic decomposition
- A repository for CAD examples
- Optimising problem formulation for cylindrical algebraic decomposition
- Cylindrical algebraic decomposition in the RegularChains library
- Recent advances in real geometric reasoning
Uses Software
This page was built for publication: Cylindrical algebraic sub-decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q475412)
