Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition

Matthew England, Russell J. Bradford, Changbo Chen, James H. Davenport, Mark Moreno Maza, David Wilson

Research output: Chapter in Book/Report/Conference proceedingChapter

17 Citations (Scopus)
122 Downloads (Pure)

Abstract

Cylindrical algebraic decompositions (CADs) are a key tool for solving problems in real algebraic geometry and beyond. We recently presented a new CAD algorithm combining two advances: truth-table invariance, making the CAD invariant with respect to the truth of logical formulae rather than the signs of polynomials; and CAD construction by regular chains technology, where first a complex decomposition is constructed by refining a tree incrementally by constraint. We here consider how best to formulate problems for input to this algorithm. We focus on a choice (not relevant for other CAD algorithms) about the order in which constraints are presented. We develop new heuristics to help make this choice and thus allow the best use of the algorithm in practice. We also consider other choices of problem formulation for CAD, as discussed in CICM 2013, revisiting these in the context of the new algorithm.
Original languageEnglish
Title of host publicationIntelligent Computer Mathematics
EditorsS. M. Watt, J. H. Davenport, A. P. Sexton, P. Sojka, J. Urban
PublisherSpringer
Pages45-60
Number of pages15
ISBN (Electronic)9783319084343
ISBN (Print)9783319084336
DOIs
Publication statusPublished - 2014

Publication series

NameLecture Notes in Artificial Intelligence
PublisherSpringer
Volume8543

Keywords

  • cylindrical algebraic decomposition
  • truth table invariance
  • regular chains
  • triangular decomposition
  • problem formulation

Fingerprint Dive into the research topics of 'Problem formulation 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., Chen, C., Davenport, J. H., Moreno Maza, M., & Wilson, D. (2014). Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. In S. M. Watt, J. H. Davenport, A. P. Sexton, P. Sojka, & J. Urban (Eds.), Intelligent Computer Mathematics (pp. 45-60). (Lecture Notes in Artificial Intelligence; Vol. 8543). Springer. https://doi.org/10.1007/978-3-319-08434-3_5