Projects per year
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.
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  13 Jun 2014 
Keywords
 cylindrical algebraic decomposition
 symbolic computation
 real algebraic geometry
 equational constraints
 computer algebra
Fingerprint Dive into the research topics of 'Cylindrical algebraic subdecompositions'. Together they form a unique fingerprint.
Projects
 1 Finished

Real Geometry and Connectedness via Triangular Description
Davenport, J., Bradford, R., England, M. & Wilson, D.
Engineering and Physical Sciences Research Council
1/10/11 → 31/12/15
Project: Research council