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

### Fingerprint

### Bibliographical note

Publisher Statement: The final publication is available at Springer via http://dx.doi.org/10.1007/s11786-014-0191-z### Keywords

- Computer algebra
- Cylindrical algebraic decomposition
- Equational constraints
- Real algebraic geometry
- Symbolic computation

### ASJC Scopus subject areas

- Applied Mathematics
- Computational Mathematics
- Computational Theory and Mathematics

### Cite this

*Mathematics in Computer Science*,

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

**Cylindrical Algebraic Sub-Decompositions.** / Wilson, D. J.; Bradford, R. J.; Davenport, J. H.; England, M.

Research output: Contribution to journal › Article

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

}

TY - JOUR

T1 - Cylindrical Algebraic Sub-Decompositions

AU - Wilson, D. J.

AU - Bradford, R. J.

AU - Davenport, J. H.

AU - England, M.

N1 - Publisher Statement: The final publication is available at Springer via http://dx.doi.org/10.1007/s11786-014-0191-z

PY - 2014

Y1 - 2014

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

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

KW - Computer algebra

KW - Cylindrical algebraic decomposition

KW - Equational constraints

KW - Real algebraic geometry

KW - Symbolic computation

U2 - 10.1007/s11786-014-0191-z

DO - 10.1007/s11786-014-0191-z

M3 - Article

VL - 8

SP - 263

EP - 288

JO - Mathematics in Computer Science

JF - Mathematics in Computer Science

SN - 1661-8270

IS - 2

ER -