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

19 Citations (Scopus)
113 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 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
Publication statusPublished - 2014

Publication series

NameLecture Notes in Computer Science
Volume8592

    Fingerprint

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