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

16 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

Fingerprint

Truth table
Triangular
Decomposition
Decompose
Invariant
Formulation
Decomposition Algorithm
Real Algebraic Geometry
Invariance
Refining
Heuristics
Polynomials
Polynomial
Geometry

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)

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

Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. / England, Matthew; Bradford, Russell; Chen, Changbo; Davenport, James H.; Maza, Marc Moreno; Wilson, David.

Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings. Vol. 8543 LNCS. ed. Springer Verlag, 2014. p. 45-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8543 LNAI).

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

England, M, Bradford, R, Chen, C, Davenport, JH, Maza, MM & 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 edn, vol. 8543 , Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8543 LNAI, Springer Verlag, pp. 45-60, 2014 International Conference on Intelligent Computer Mathematics, Coimbra, Portugal, 7/07/14. https://doi.org/10.1007/978-3-319-08434-3_5
England M, Bradford R, Chen C, Davenport JH, Maza MM, Wilson D. 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 . Springer Verlag. 2014. p. 45-60. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-08434-3_5
England, Matthew ; Bradford, Russell ; Chen, Changbo ; Davenport, James H. ; Maza, Marc Moreno ; Wilson, David. / Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings. Vol. 8543 LNCS. ed. Springer Verlag, 2014. pp. 45-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{74fae35d14e94911b4247027611a0ddb,
title = "Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition",
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.",
keywords = "cylindrical algebraic decomposition, problem formulation, regular chains, triangular decomposition, truth table invariance",
author = "Matthew England and Russell Bradford and Changbo Chen and Davenport, {James H.} and Maza, {Marc Moreno} and David Wilson",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/978-3319-08434-3_5 Copyright {\circledC} 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.",
year = "2014",
doi = "10.1007/978-3-319-08434-3_5",
language = "English",
isbn = "978-3-319-08433-6",
volume = "8543",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "45--60",
booktitle = "Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings",
address = "Austria",
edition = "LNCS",

}

TY - GEN

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

AU - England, Matthew

AU - Bradford, Russell

AU - Chen, Changbo

AU - Davenport, James H.

AU - Maza, Marc Moreno

AU - Wilson, David

N1 - 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.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - cylindrical algebraic decomposition

KW - problem formulation

KW - regular chains

KW - triangular decomposition

KW - truth table invariance

U2 - 10.1007/978-3-319-08434-3_5

DO - 10.1007/978-3-319-08434-3_5

M3 - Conference proceeding

SN - 978-3-319-08433-6

VL - 8543

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 45

EP - 60

BT - Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings

PB - Springer Verlag

ER -