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 in Book/Report/Conference proceedingConference contribution

12 Citations (Scopus)
130 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
Subtitle of host publication4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings
PublisherSpringer
Pages450-457
Number of pages8
Volume8592
ISBN (Print)978-3-662-44198-5
DOIs
Publication statusPublished - 2014

Fingerprint Dive into the research topics of 'Choosing a variable ordering for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition'. Together they form a unique fingerprint.

  • Projects

  • 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