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

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

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

17 Citations (Scopus)
6 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 - International Conference, CICM 2014, Proceedings
PublisherSpringer Verlag
Pages45-60
Number of pages16
Volume8543
EditionLNCS
ISBN (Electronic)978-3-319-08434-3
ISBN (Print)978-3-319-08433-6
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event2014 International Conference on Intelligent Computer Mathematics - Coimbra, Portugal
Duration: 7 Jul 201411 Jul 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8543 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference2014 International Conference on Intelligent Computer Mathematics
Abbreviated titleCICM 2014
CountryPortugal
CityCoimbra
Period7/07/1411/07/14

Bibliographical note

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3319-08434-3_5


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.

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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.

  • Cite this

    England, M., Bradford, R., Chen, C., Davenport, J. H., Maza, M. M., & Wilson, D. (2014). Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. In Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings (LNCS ed., Vol. 8543 , pp. 45-60). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8543 LNAI). Springer Verlag. https://doi.org/10.1007/978-3-319-08434-3_5