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

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

doi:10.1007/978-3-662-44199-2_68

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

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

University of Bath

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

16 Citations (Scopus)

37 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 language	English
Title of host publication	Mathematical Software, ICMS 2014 - 4th International Congress, Proceedings
Place of Publication	Berlin
Publisher	Springer Verlag
Pages	450-457
Number of pages	8
Volume	8592 LNCS
ISBN (Print)	9783662441985
DOIs	https://doi.org/10.1007/978-3-662-44199-2_68
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)
Volume	8592 LNCS
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_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)

Access to Document

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

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

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

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)). doi: 10.1007/978-3-662-44199-2_68

England, Matthew ; Bradford, Russell ; Davenport, James H. et al. / 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 {\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_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",

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

}

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

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

AN - SCOPUS:84905853225

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

T2 - International Congress on Mathematical Software

Y2 - 5 August 2014 through 9 August 2014

ER -

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

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this