Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting

Matthew England; David Wilson; Russell Bradford; James H. Davenport

doi:10.1007/978-3-662-44199-2_69

Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting

Matthew England, David Wilson, Russell Bradford, James H. Davenport

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

20 Citations (SciVal)

173 Downloads (Pure)

Abstract

Cylindrical algebraic decomposition (CAD) is an important tool, both for quantifier elimination over the reals and a range of other applications. Traditionally, a CAD is built through a process of projection and lifting to move the problem within Euclidean spaces of changing dimension. Recently, an alternative approach which first decomposes complex space using triangular decomposition before refining to real space has been introduced and implemented within the RegularChains Library of Maple. We here describe a freely available package ProjectionCAD which utilises the routines within the RegularChains Library to build CADs by projection and lifting. We detail how the projection and lifting algorithms were modified to allow this, discuss the motivation and survey the functionality of the package.

Original language	English
Title of host publication	Mathematical Software – ICMS 2014
Subtitle of host publication	4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings
Editors	H. Hong, C. Yap
Publisher	Springer
Pages	458-465
Number of pages	8
ISBN (Print)	9783662441985
DOIs	https://doi.org/10.1007/978-3-662-44199-2_69
Publication status	Published - 2014

Publication series

Name	Lecture Notes in Computer Science
Volume	8592

Access to Document

10.1007/978-3-662-44199-2_69

EWBD14Accepted author manuscript, 246 KB

Cite this

England, M., Wilson, D., Bradford, R., & Davenport, J. H. (2014). Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting. In H. Hong, & C. Yap (Eds.), Mathematical Software – ICMS 2014: 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings (pp. 458-465). (Lecture Notes in Computer Science; Vol. 8592). Springer. https://doi.org/10.1007/978-3-662-44199-2_69

Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting. / England, Matthew; Wilson, David; Bradford, Russell et al.
Mathematical Software – ICMS 2014: 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings. ed. / H. Hong; C. Yap. Springer, 2014. p. 458-465 (Lecture Notes in Computer Science; Vol. 8592).

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

England, M, Wilson, D, Bradford, R & Davenport, JH 2014, Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting. in H Hong & C Yap (eds), Mathematical Software – ICMS 2014: 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings. Lecture Notes in Computer Science, vol. 8592, Springer, pp. 458-465. https://doi.org/10.1007/978-3-662-44199-2_69

England M, Wilson D, Bradford R , Davenport JH. Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting. In Hong H, Yap C, editors, Mathematical Software – ICMS 2014: 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings. Springer. 2014. p. 458-465. (Lecture Notes in Computer Science). doi: 10.1007/978-3-662-44199-2_69

England, Matthew ; Wilson, David ; Bradford, Russell et al. / Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting. Mathematical Software – ICMS 2014: 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings. editor / H. Hong ; C. Yap. Springer, 2014. pp. 458-465 (Lecture Notes in Computer Science).

@inproceedings{4f3419dbafc34bdaacf66ec013b00551,

title = "Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting",

abstract = "Cylindrical algebraic decomposition (CAD) is an important tool, both for quantifier elimination over the reals and a range of other applications. Traditionally, a CAD is built through a process of projection and lifting to move the problem within Euclidean spaces of changing dimension. Recently, an alternative approach which first decomposes complex space using triangular decomposition before refining to real space has been introduced and implemented within the RegularChains Library of Maple. We here describe a freely available package ProjectionCAD which utilises the routines within the RegularChains Library to build CADs by projection and lifting. We detail how the projection and lifting algorithms were modified to allow this, discuss the motivation and survey the functionality of the package.",

author = "Matthew England and David Wilson and Russell Bradford and Davenport, {James H.}",

year = "2014",

doi = "10.1007/978-3-662-44199-2_69",

language = "English",

isbn = "9783662441985",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "458--465",

editor = "H. Hong and C. Yap",

booktitle = "Mathematical Software – ICMS 2014",

}

TY - GEN

T1 - Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting

AU - England, Matthew

AU - Wilson, David

AU - Bradford, Russell

AU - Davenport, James H.

PY - 2014

Y1 - 2014

N2 - Cylindrical algebraic decomposition (CAD) is an important tool, both for quantifier elimination over the reals and a range of other applications. Traditionally, a CAD is built through a process of projection and lifting to move the problem within Euclidean spaces of changing dimension. Recently, an alternative approach which first decomposes complex space using triangular decomposition before refining to real space has been introduced and implemented within the RegularChains Library of Maple. We here describe a freely available package ProjectionCAD which utilises the routines within the RegularChains Library to build CADs by projection and lifting. We detail how the projection and lifting algorithms were modified to allow this, discuss the motivation and survey the functionality of the package.

AB - Cylindrical algebraic decomposition (CAD) is an important tool, both for quantifier elimination over the reals and a range of other applications. Traditionally, a CAD is built through a process of projection and lifting to move the problem within Euclidean spaces of changing dimension. Recently, an alternative approach which first decomposes complex space using triangular decomposition before refining to real space has been introduced and implemented within the RegularChains Library of Maple. We here describe a freely available package ProjectionCAD which utilises the routines within the RegularChains Library to build CADs by projection and lifting. We detail how the projection and lifting algorithms were modified to allow this, discuss the motivation and survey the functionality of the package.

UR - http://dx.doi.org/10.1007/978-3-662-44199-2_69

U2 - 10.1007/978-3-662-44199-2_69

DO - 10.1007/978-3-662-44199-2_69

M3 - Chapter in a published conference proceeding

SN - 9783662441985

T3 - Lecture Notes in Computer Science

SP - 458

EP - 465

BT - Mathematical Software – ICMS 2014

A2 - Hong, H.

A2 - Yap, C.

PB - Springer

ER -

Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Real Geometry and Connectedness via Triangular Description

Cite this

Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Projects

Real Geometry and Connectedness via Triangular Description

Cite this