Cylindrical algebraic sub-decompositions

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

doi:10.1007/s11786-014-0191-z

Cylindrical algebraic sub-decompositions

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

Research output: Contribution to journal › Article › peer-review

17 Citations (SciVal)

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 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	https://doi.org/10.1007/s11786-014-0191-z
Publication status	Published - 13 Jun 2014

Keywords

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

Access to Document

10.1007/s11786-014-0191-zLicence: CC BY

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

Russell Bradford
- Mathematical Foundations of Computation
Person: Research & Teaching

Cite this

@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 = jun,

day = "13",

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/13

Y1 - 2014/6/13

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

U2 - 10.1007/s11786-014-0191-z

DO - 10.1007/s11786-014-0191-z

M3 - Article

SN - 1661-8270

VL - 8

SP - 263

EP - 288

JO - Mathematics in Computer Science

JF - Mathematics in Computer Science

IS - 2

ER -

Cylindrical algebraic sub-decompositions

Abstract

Keywords

Access to Document

Fingerprint

Projects

Real Geometry and Connectedness via Triangular Description

Profiles

Russell Bradford

Cite this