Cylindrical algebraic sub-decompositions

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

Research output: Contribution to journalArticle

  • 9 Citations

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.
LanguageEnglish
Pages263-288
Number of pages26
JournalMathematics in Computer Science
Volume8
Issue number2
Early online date13 Jun 2014
DOIs
StatusPublished - Jun 2014

Fingerprint

Decomposition
Decompose
Real Algebraic Geometry
Truth table
Semi-algebraic Sets
Complexity Analysis
Maple
Cell
Quantifiers
Experimentation
Higher Dimensions
Subset
Invariant
Geometry

Keywords

  • cylindrical algebraic decomposition
  • symbolic computation
  • real algebraic geometry
  • equational constraints
  • computer algebra

Cite this

Cylindrical algebraic sub-decompositions. / Wilson, D.; Bradford, R.; Davenport, J. H.; England, M.

In: Mathematics in Computer Science, Vol. 8, No. 2, 06.2014, p. 263-288.

Research output: Contribution to journalArticle

@article{d2cd9ddfae3b491498a4c9909e48f890,
title = "Cylindrical algebraic sub-decompositions",
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.",
keywords = "cylindrical algebraic decomposition, symbolic computation, real algebraic geometry, equational constraints, computer algebra",
author = "D. Wilson and R. Bradford and Davenport, {J. H.} and M. England",
year = "2014",
month = "6",
doi = "10.1007/s11786-014-0191-z",
language = "English",
volume = "8",
pages = "263--288",
journal = "Mathematics in Computer Science",
issn = "1661-8270",
publisher = "Birkhauser Verlag Basel",
number = "2",

}

TY - JOUR

T1 - Cylindrical algebraic sub-decompositions

AU - Wilson, D.

AU - Bradford, R.

AU - Davenport, J. H.

AU - England, M.

PY - 2014/6

Y1 - 2014/6

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 - cylindrical algebraic decomposition

KW - symbolic computation

KW - real algebraic geometry

KW - equational constraints

KW - computer algebra

UR - http://www.scopus.com/inward/record.url?scp=84902022670&partnerID=8YFLogxK

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

T2 - Mathematics in Computer Science

JF - Mathematics in Computer Science

SN - 1661-8270

IS - 2

ER -