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.
| Original language | English |
|---|---|
| Pages (from-to) | 263-288 |
| Number of pages | 26 |
| Journal | Mathematics in Computer Science |
| Volume | 8 |
| Issue number | 2 |
| Early online date | 13 Jun 2014 |
| DOIs | |
| Publication status | Published - 2014 |
| Externally published | Yes |
Bibliographical note
Publisher Statement: The final publication is available at Springer via http://dx.doi.org/10.1007/s11786-014-0191-zKeywords
- Computer algebra
- Cylindrical algebraic decomposition
- Equational constraints
- Real algebraic geometry
- Symbolic computation
ASJC Scopus subject areas
- Applied Mathematics
- Computational Mathematics
- Computational Theory and Mathematics
Fingerprint
Dive into the research topics of 'Cylindrical Algebraic Sub-Decompositions'. Together they form a unique fingerprint.Profiles
-
Matthew England
- Research Centre for Computational Science and Mathematical Modelling - Associate Professor Academic, Centre Director
Person: Teaching and Research, Professional Services