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

University of Bath

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding › peer-review

20 Citations (Scopus)

39 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	International Congress on Mathematical Software
Subtitle of host publication	ICMS 2014: Mathematical Software – ICMS 2014
Editors	Hoon Hong, Chee Yap
Place of Publication	Berlin
Publisher	Springer Verlag
Pages	458-465
Number of pages	8
Volume	8592
ISBN (Electronic)	978-3-662-44199-2
ISBN (Print)	978-3-662-44198-5
DOIs	https://doi.org/10.1007/978-3-662-44199-2_69
Publication status	Published - 2014
Externally published	Yes
Event	International Congress on Mathematical Software - Hanyang University, Seoul, Korea, Republic of Duration: 5 Aug 2014 → 9 Aug 2014 Conference number: 4 http://voronoi.hanyang.ac.kr/icms2014/ (Link to conference website)

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	8592
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	International Congress on Mathematical Software
Abbreviated title	ICMS 2014
Country/Territory	Korea, Republic of
City	Seoul
Period	5/08/14 → 9/08/14
Internet address	http://voronoi.hanyang.ac.kr/icms2014/ (Link to conference website)

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)

Access to Document

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

Post-PrintAccepted author manuscript, 728 KBLicence: CC BY-NC

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). 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 et al.
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 proceeding › Conference proceeding › peer-review

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)). 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. 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 {\textcopyright} 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. ; International Congress on Mathematical Software, ICMS 2014 ; Conference date: 05-08-2014 Through 09-08-2014",

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",

url = "http://voronoi.hanyang.ac.kr/icms2014/",

}

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 - Conference code: 4

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

AN - SCOPUS:84905845341

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

T2 - International Congress on Mathematical Software

Y2 - 5 August 2014 through 9 August 2014

ER -

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

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this