Cylindrical Algebraic Sub-Decompositions
arXiv:1401.0647 · doi:10.1007/s11786-014-0191-z
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.
arXiv comment26 pages
References in corpus (3)
Cited by in corpus (13)
- Truth Table Invariant Cylindrical Algebraic Decomposition
- Deciding the Consistency of Non-Linear Real Arithmetic Constraints with a Conflict Driven Search Using Cylindrical Algebraic Coverings
- Truth Table Invariant Cylindrical Algebraic Decomposition by Regular Chains
- Identifying the Parametric Occurrence of Multiple Steady States for some Biological Networks
- Using the Regular Chains Library to build cylindrical algebraic decompositions by projecting and lifting
- Cylindrical Algebraic Decomposition with Equational Constraints
- Using Machine Learning to Improve Cylindrical Algebraic Decomposition
- The complexity of cylindrical algebraic decomposition with respect to polynomial degree
- Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition
- Using the distribution of cells by dimension in a cylindrical algebraic decomposition
- Need Polynomial Systems be Doubly-exponential?
- Polynomial Superlevel Set Representation of the Multistationarity Region of Chemical Reaction Networks
- Recent Advances in Real Geometric Reasoning