Abstract
Cylindrical algebraic decompositions (CADs) are a key tool in real algebraic geometry, used primarily for eliminating quantifiers over the reals and studying semialgebraic sets. In this paper we introduce cylindrical algebraic subdecompositions (subCADs), which are subsets of CADs containing all the information needed to specify a solution for a given problem. We define two new types of subCAD: variety subCADs which are those cells in a CAD lying on a designated variety; and layered subCADs 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 truthtable 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 (fromto)  263288 
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/s117860140191zKeywords
 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 SubDecompositions'. Together they form a unique fingerprint.
Profiles

Matthew England
 Faculty Research Centre for Data Science  Associate Professor (Academic)
Person: Teaching and Research