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

M England; R.J. Bradford; J.H. Davenport; D. 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

M England, R.J. Bradford, J.H. Davenport, D. Wilson

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

16 Citations (SciVal)

166 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
Subtitle of host publication	4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings
Publisher	Springer
Pages	450-457
Number of pages	8
Volume	8592
ISBN (Print)	978-3-662-44198-5
DOIs	https://doi.org/10.1007/978-3-662-44199-2_68
Publication status	Published - 2014

Access to Document

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

EBDW14Accepted author manuscript, 221 KB

Cite this

England, M., Bradford, R. J., 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, Seoul, South Korea, August 5-9, 2014. Proceedings (Vol. 8592, pp. 450-457). Springer. 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, M; Bradford, R.J.; Davenport, J.H. et al.
Mathematical Software – ICMS 2014: 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings. Vol. 8592 Springer, 2014. p. 450-457.

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

England, M, Bradford, RJ , 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, Seoul, South Korea, August 5-9, 2014. Proceedings. vol. 8592, Springer, pp. 450-457. https://doi.org/10.1007/978-3-662-44199-2_68

England M, Bradford RJ , 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, Seoul, South Korea, August 5-9, 2014. Proceedings. Vol. 8592. Springer. 2014. p. 450-457 doi: 10.1007/978-3-662-44199-2_68

@inproceedings{c9c58a7758a946e6aefe0a7e7ea95fc5,

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 = "M England and R.J. Bradford and J.H. Davenport and D. Wilson",

year = "2014",

doi = "10.1007/978-3-662-44199-2_68",

language = "English",

isbn = "978-3-662-44198-5",

volume = "8592",

pages = "450--457",

booktitle = "Mathematical Software – ICMS 2014",

publisher = "Springer",

}

TY - GEN

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

AU - England, M

AU - Bradford, R.J.

AU - Davenport, J.H.

AU - Wilson, D.

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.

UR - http://dx.doi.org/10.1007/978-3-662-44199-2_68

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

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

M3 - Chapter in a published conference proceeding

SN - 978-3-662-44198-5

VL - 8592

SP - 450

EP - 457

BT - Mathematical Software – ICMS 2014

PB - Springer

ER -

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

Abstract

Access to Document

Other files and links

Fingerprint

Real Geometry and Connectedness via Triangular Description

Cite this

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

Abstract

Access to Document

Other files and links

Fingerprint

Projects

Real Geometry and Connectedness via Triangular Description

Cite this