Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition

Matthew England, Russell Bradford, James H. Davenport, David Wilson

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

8 Citations (Scopus)
9 Downloads (Pure)

Abstract

Cylindrical algebraic decomposition (CAD) is a key tool for solving problems in real algebraic geometry and beyond. In recent years a new approach has been developed, where regular chains technology is used to first build a decomposition in complex space. We consider the latest variant of this which builds the complex decomposition incrementally by polynomial and produces CADs on whose cells a sequence of formulae are truth-invariant. Like all CAD algorithms the user must provide a variable ordering which can have a profound impact on the tractability of a problem. We evaluate existing heuristics to help with the choice for this algorithm, suggest improvements and then derive a new heuristic more closely aligned with the mechanics of the new algorithm.

Original languageEnglish
Title of host publicationMathematical Software, ICMS 2014 - 4th International Congress, Proceedings
Place of PublicationBerlin
PublisherSpringer Verlag
Pages450-457
Number of pages8
Volume8592 LNCS
ISBN (Print)9783662441985
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)
Volume8592 LNCS
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

Truth table
Triangular
Decomposition
Decompose
Invariant
Real Algebraic Geometry
Heuristics
Tractability
Decomposition Algorithm
Mechanics
Computer aided design
Polynomial
Evaluate
Cell
Polynomials
Geometry

Bibliographical note

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-
662-44199-2_68
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., Bradford, R., Davenport, J. H., & Wilson, D. (2014). Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. In Mathematical Software, ICMS 2014 - 4th International Congress, Proceedings (Vol. 8592 LNCS, pp. 450-457). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8592 LNCS). Berlin: Springer Verlag. https://doi.org/10.1007/978-3-662-44199-2_68

Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. / England, Matthew; Bradford, Russell; Davenport, James H.; Wilson, David.

Mathematical Software, ICMS 2014 - 4th International Congress, Proceedings. Vol. 8592 LNCS Berlin : Springer Verlag, 2014. p. 450-457 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8592 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

England, M, Bradford, R, Davenport, JH & Wilson, D 2014, Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. in Mathematical Software, ICMS 2014 - 4th International Congress, Proceedings. vol. 8592 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8592 LNCS, Springer Verlag, Berlin, pp. 450-457, International Congress on Mathematical Software, Seoul, Korea, Republic of, 5/08/14. https://doi.org/10.1007/978-3-662-44199-2_68
England M, Bradford R, Davenport JH, Wilson D. Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. In Mathematical Software, ICMS 2014 - 4th International Congress, Proceedings. Vol. 8592 LNCS. Berlin: Springer Verlag. 2014. p. 450-457. (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_68
England, Matthew ; Bradford, Russell ; Davenport, James H. ; Wilson, David. / Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. Mathematical Software, ICMS 2014 - 4th International Congress, Proceedings. Vol. 8592 LNCS Berlin : Springer Verlag, 2014. pp. 450-457 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{d16c42186fda4606829410ad50bd7ed7,
title = "Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition",
abstract = "Cylindrical algebraic decomposition (CAD) is a key tool for solving problems in real algebraic geometry and beyond. In recent years a new approach has been developed, where regular chains technology is used to first build a decomposition in complex space. We consider the latest variant of this which builds the complex decomposition incrementally by polynomial and produces CADs on whose cells a sequence of formulae are truth-invariant. Like all CAD algorithms the user must provide a variable ordering which can have a profound impact on the tractability of a problem. We evaluate existing heuristics to help with the choice for this algorithm, suggest improvements and then derive a new heuristic more closely aligned with the mechanics of the new algorithm.",
author = "Matthew England and Russell Bradford and Davenport, {James H.} and David Wilson",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/978-3- 662-44199-2_68 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_68",
language = "English",
isbn = "9783662441985",
volume = "8592 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "450--457",
booktitle = "Mathematical Software, ICMS 2014 - 4th International Congress, Proceedings",
address = "Austria",

}

TY - GEN

T1 - Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition

AU - England, Matthew

AU - Bradford, Russell

AU - Davenport, James H.

AU - Wilson, David

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/978-3- 662-44199-2_68 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 a key tool for solving problems in real algebraic geometry and beyond. In recent years a new approach has been developed, where regular chains technology is used to first build a decomposition in complex space. We consider the latest variant of this which builds the complex decomposition incrementally by polynomial and produces CADs on whose cells a sequence of formulae are truth-invariant. Like all CAD algorithms the user must provide a variable ordering which can have a profound impact on the tractability of a problem. We evaluate existing heuristics to help with the choice for this algorithm, suggest improvements and then derive a new heuristic more closely aligned with the mechanics of the new algorithm.

AB - Cylindrical algebraic decomposition (CAD) is a key tool for solving problems in real algebraic geometry and beyond. In recent years a new approach has been developed, where regular chains technology is used to first build a decomposition in complex space. We consider the latest variant of this which builds the complex decomposition incrementally by polynomial and produces CADs on whose cells a sequence of formulae are truth-invariant. Like all CAD algorithms the user must provide a variable ordering which can have a profound impact on the tractability of a problem. We evaluate existing heuristics to help with the choice for this algorithm, suggest improvements and then derive a new heuristic more closely aligned with the mechanics of the new algorithm.

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

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

M3 - Conference proceeding

SN - 9783662441985

VL - 8592 LNCS

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

SP - 450

EP - 457

BT - Mathematical Software, ICMS 2014 - 4th International Congress, Proceedings

PB - Springer Verlag

CY - Berlin

ER -