Truth table invariant cylindrical algebraic decomposition by regular chains

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

Research output: Chapter in Book/Report/Conference proceedingChapter

17 Citations (Scopus)
317 Downloads (Pure)

Abstract

A new algorithm to compute cylindrical algebraic decompositions (CADs) is presented, building on two recent advances. Firstly, the output is truth table invariant (a TTICAD) meaning given formulae have constant truth value on each cell of the decomposition. Secondly, the computation uses regular chains theory to first build a cylindrical decomposition of complex space (CCD) incrementally by polynomial. Significant modification of the regular chains technology was used to achieve the more sophisticated invariance criteria. Experimental results on an implementation in the RegularChains Library for Maple verify that combining these advances gives an algorithm superior to its individual components and competitive with the state of the art.
Original languageEnglish
Title of host publicationComputer Algebra in Scientific Computing
Subtitle of host publicationProceedings of the16th International Workshop, CASC 2014, Warsaw, Poland, September 8-12, 2014
EditorsV. P. Gerdt, W. Koepf, W. M. Seiler, E. V. Vorozhtsov
PublisherSpringer
Pages44-58
Number of pages15
Volume8660
ISBN (Print)9783319105147
DOIs
Publication statusPublished - 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer

Keywords

  • cylindrical algebraic decomposition
  • equational constraint
  • regular chains
  • triangular decomposition

Fingerprint Dive into the research topics of 'Truth table invariant cylindrical algebraic decomposition by regular chains'. Together they form a unique fingerprint.

  • Projects

  • Profiles

    No photo of Russell Bradford

    Cite this

    Bradford, R., Chen, C., Davenport, J. H., England, M., Moreno Maza, M., & Wilson, D. (2014). Truth table invariant cylindrical algebraic decomposition by regular chains. In V. P. Gerdt, W. Koepf, W. M. Seiler, & E. V. Vorozhtsov (Eds.), Computer Algebra in Scientific Computing: Proceedings of the16th International Workshop, CASC 2014, Warsaw, Poland, September 8-12, 2014 (Vol. 8660, pp. 44-58). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/978-3-319-10515-4_4