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

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 - 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 sub-decompositions'. 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

## Profiles

## Cite this

Wilson, D., Bradford, R., Davenport, J. H., & England, M. (2014). Cylindrical algebraic sub-decompositions.

*Mathematics in Computer Science*,*8*(2), 263-288. https://doi.org/10.1007/s11786-014-0191-z