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

doi:10.1007/978-3-319-08434-3_5

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 proceeding › Conference proceeding › peer-review

17 Citations (Scopus)

28 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 language	English
Title of host publication	Intelligent Computer Mathematics - International Conference, CICM 2014, Proceedings
Publisher	Springer Verlag
Pages	45-60
Number of pages	16
Volume	8543
Edition	LNCS
ISBN (Electronic)	978-3-319-08434-3
ISBN (Print)	978-3-319-08433-6
DOIs	https://doi.org/10.1007/978-3-319-08434-3_5
Publication status	Published - 2014
Externally published	Yes
Event	2014 International Conference on Intelligent Computer Mathematics - Coimbra, Portugal Duration: 7 Jul 2014 → 11 Jul 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8543 LNAI
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	2014 International Conference on Intelligent Computer Mathematics
Abbreviated title	CICM 2014
Country/Territory	Portugal
City	Coimbra
Period	7/07/14 → 11/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)

Access to Document

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

Post-PrintAccepted author manuscript, 1.38 MBLicence: CC BY-NC

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 et al.
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 proceeding › Conference proceeding › peer-review

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)). doi: 10.1007/978-3-319-08434-3_5

England, Matthew ; Bradford, Russell ; Chen, Changbo et al. / 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 {\textcopyright} 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. ; 2014 International Conference on Intelligent Computer Mathematics, CICM 2014 ; Conference date: 07-07-2014 Through 11-07-2014",

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

AN - SCOPUS:84904175578

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

T2 - 2014 International Conference on Intelligent Computer Mathematics

Y2 - 7 July 2014 through 11 July 2014

ER -

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

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this