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 proceeding

15 Citations (Scopus)
5 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 publicationInternational Congress on Mathematical Software
Subtitle of host publicationICMS 2014: Mathematical Software – ICMS 2014
EditorsHoon Hong, Chee Yap
Place of PublicationBerlin
PublisherSpringer Verlag
Pages458-465
Number of pages8
Volume8592
ISBN (Electronic)978-3-662-44199-2
ISBN (Print)978-3-662-44198-5
DOIs
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
http://voronoi.hanyang.ac.kr/icms2014/ (Link to conference website)

Publication series

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

Conference

ConferenceInternational Congress on Mathematical Software
Abbreviated titleICMS 2014
CountryKorea, Republic of
CitySeoul
Period5/08/149/08/14
Internet address

Fingerprint

Decomposition
Decompose
Projection
Quantifier Elimination
Refining
Maple
Computer aided design
Euclidean space
Triangular
Libraries
Alternatives
Range of data

Bibliographical note

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-44199-2_69


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)

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.), International Congress on Mathematical Software: ICMS 2014: Mathematical Software – ICMS 2014 (Vol. 8592, pp. 458-465). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8592). Berlin: Springer Verlag. 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.

International Congress on Mathematical Software: ICMS 2014: Mathematical Software – ICMS 2014. ed. / Hoon Hong; Chee Yap. Vol. 8592 Berlin : Springer Verlag, 2014. p. 458-465 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8592).

Research output: Chapter in Book/Report/Conference proceedingConference 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), International Congress on Mathematical Software: ICMS 2014: Mathematical Software – ICMS 2014. vol. 8592, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8592, Springer Verlag, Berlin, pp. 458-465, International Congress on Mathematical Software, Seoul, Korea, Republic of, 5/08/14. 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, International Congress on Mathematical Software: ICMS 2014: Mathematical Software – ICMS 2014. Vol. 8592. Berlin: Springer Verlag. 2014. p. 458-465. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). 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. International Congress on Mathematical Software: ICMS 2014: Mathematical Software – ICMS 2014. editor / Hoon Hong ; Chee Yap. Vol. 8592 Berlin : Springer Verlag, 2014. pp. 458-465 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{6d0791649cb142d39f9a3ce7f5891b83,
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.}",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-44199-2_69 Copyright {\circledC} 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.",
year = "2014",
doi = "10.1007/978-3-662-44199-2_69",
language = "English",
isbn = "978-3-662-44198-5",
volume = "8592",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "458--465",
editor = "Hoon Hong and Chee Yap",
booktitle = "International Congress on Mathematical Software",
address = "Austria",

}

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.

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-44199-2_69 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.

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.

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

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

M3 - Conference proceeding

SN - 978-3-662-44198-5

VL - 8592

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 458

EP - 465

BT - International Congress on Mathematical Software

A2 - Hong, Hoon

A2 - Yap, Chee

PB - Springer Verlag

CY - Berlin

ER -