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.
26 pages
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