Cylindrical algebraic sub-decompositions

D. Wilson, R. Bradford, J. H. Davenport, M. England

Research output: Contribution to journalArticle

14 Citations (Scopus)
85 Downloads (Pure)

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 languageEnglish
Pages (from-to)263-288
Number of pages26
JournalMathematics in Computer Science
Volume8
Issue number2
Early online date13 Jun 2014
DOIs
Publication statusPublished - 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

  • Profiles

    No photo of Russell Bradford

    Cite this