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 proceedingpeer-review

19 Citations (Scopus)
20 Downloads (Pure)


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 publicationInternational Congress on Mathematical Software
Subtitle of host publicationICMS 2014: Mathematical Software – ICMS 2014
EditorsHoon Hong, Chee Yap
Place of PublicationBerlin
PublisherSpringer Verlag
Number of pages8
ISBN (Electronic)978-3-662-44199-2
ISBN (Print)978-3-662-44198-5
Publication statusPublished - 2014
Externally publishedYes
EventInternational Congress on Mathematical Software - Hanyang University, Seoul, Korea, Republic of
Duration: 5 Aug 20149 Aug 2014
Conference number: 4 (Link to conference website)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)03029743
ISSN (Electronic)16113349


ConferenceInternational Congress on Mathematical Software
Abbreviated titleICMS 2014
Country/TerritoryKorea, Republic of
Internet address

Bibliographical note

The final publication is available at Springer via

Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Using the regular chains library to build cylindrical algebraic decompositions by projecting and lifting'. Together they form a unique fingerprint.

Cite this