Cylindrical algebraic sub-decompositions
From MaRDI portal
Publication:475412
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1157658 (Why is no real title available?)
- scientific article; zbMATH DE number 2151206 (Why is no real title available?)
- scientific article; zbMATH DE number 2151213 (Why is no real title available?)
- A :20piano movers' '
- Algorithmic methods for investigating equilibria in epidemic modeling
- An effective implementation of a symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
- An incremental algorithm for computing cylindrical algebraic decompositions
- Computation with semialgebraic sets represented by cylindrical algebraic formulas
- Computing cylindrical algebraic decomposition via triangular decomposition
- Constructing a single open cell in a cylindrical algebraic decomposition
- Cylindrical Algebraic Decomposition I: The Basic Algorithm
- Cylindrical algebraic decomposition using validated numerics
- Cylindrical algebraic decompositions for Boolean combinations
- Efficient projection orders for CAD
- Geometry of branch cuts
- Improved projection for cylindrical algebraic decomposition
- MetiTarski: past and future
- On propagation of equational constraints in CAD-based quantifier elimination
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- On using bi-equational constraints in CAD construction
- Optimising problem formulation for cylindrical algebraic decomposition
- Partial cylindrical algebraic decomposition for quantifier elimination
- QEPCAD B
- Real quantifier elimination is doubly exponential
- Solving Polynomial Strict Inequalities Using Cylindrical Algebraic Decomposition
- Solving polynomial systems over semialgebraic sets represented by cylindrical algebraic formulas
- Solving systems of strict polynomial inequalities
- The complexity of quantifier elimination and cylindrical algebraic decomposition
- Truth table invariant cylindrical algebraic decomposition
- Understanding branch cuts of expressions
Cited in
(22)- Cylindrical algebraic decomposition with equational constraints
- On delineability of varieties in CAD-based quantifier elimination with two equational constraints
- On proving inequalities by cylindrical algebraic decomposition
- CAD and topology of semi-algebraic sets
- Properness defects and projections and computation of at least one point in each connected component of a real algebraic set
- Using machine learning to improve cylindrical algebraic decomposition
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- Cylindrical algebraic decomposition in the RegularChains library
- Open non-uniform cylindrical algebraic decompositions
- Computing cylindrical algebraic decomposition via triangular decomposition
- Truth table invariant cylindrical algebraic decomposition
- Cylindrical algebraic decomposition using validated numerics
- Identifying the parametric occurrence of multiple steady states for some biological networks
- Solving polynomial systems over semialgebraic sets represented by cylindrical algebraic formulas
- Optimising problem formulation for cylindrical algebraic decomposition
- Need polynomial systems be doubly-exponential?
- A repository for CAD examples
- Recent advances in real geometric reasoning
- Deciding the consistency of non-linear real arithmetic constraints with a conflict driven search using cylindrical algebraic coverings
- On Approximations and Incidence in Cylindrical Algebraic Decompositions
- Constructing a single cell in cylindrical algebraic decomposition
- An approximate characterisation of the set of feasible trajectories for constrained flat systems
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)
