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 in Book/Report/Conference proceedingConference contribution

  • 10 Citations

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.
LanguageEnglish
Title of host publicationMathematical Software – ICMS 2014
Subtitle of host publication4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings
EditorsH. Hong, C. Yap
PublisherSpringer
Pages458-465
Number of pages8
ISBN (Print)9783662441985
DOIs
StatusPublished - 2014

Publication series

NameLecture Notes in Computer Science
Volume8592

Fingerprint

Decomposition
Refining
Computer aided design

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; Davenport, James H.

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 in Book/Report/Conference proceedingConference contribution

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). https://doi.org/10.1007/978-3-662-44199-2_69
England, Matthew ; Wilson, David ; Bradford, Russell ; Davenport, James H. / 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 - Conference contribution

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 -