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

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 J. Bradford, Changbo Chen, James H. Davenport, Mark Moreno Maza, David Wilson

Research output: Chapter or section in a book/report/conference proceeding › Chapter or section

17 Citations (SciVal)

183 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
Editors	S. M. Watt, J. H. Davenport, A. P. Sexton, P. Sojka, J. Urban
Publisher	Springer
Pages	45-60
Number of pages	15
ISBN (Electronic)	9783319084343
ISBN (Print)	9783319084336
DOIs	https://doi.org/10.1007/978-3-319-08434-3_5
Publication status	Published - 2014

Publication series

Name	Lecture Notes in Artificial Intelligence
Publisher	Springer
Volume	8543

Keywords

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

Access to Document

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

EBCDMW14
The final publication will be available from http://link.springer.com/
Accepted author manuscript, 842 KB

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

Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. / England, Matthew; Bradford, Russell J.; Chen, Changbo et al.
Intelligent Computer Mathematics. ed. / S. M. Watt; J. H. Davenport; A. P. Sexton; P. Sojka; J. Urban. Springer, 2014. p. 45-60 (Lecture Notes in Artificial Intelligence; Vol. 8543).

Research output: Chapter or section in a book/report/conference proceeding › Chapter or section

England, M, Bradford, RJ, Chen, C, Davenport, JH, Moreno Maza, M & Wilson, D 2014, Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. in SM Watt, JH Davenport, AP Sexton, P Sojka & J Urban (eds), Intelligent Computer Mathematics. Lecture Notes in Artificial Intelligence, vol. 8543, Springer, pp. 45-60. https://doi.org/10.1007/978-3-319-08434-3_5

England M, Bradford RJ, Chen C, Davenport JH, Moreno Maza M, Wilson D. Problem formulation for truth-table invariant cylindrical algebraic decomposition by incremental triangular decomposition. In Watt SM, Davenport JH, Sexton AP, Sojka P, Urban J, editors, Intelligent Computer Mathematics. Springer. 2014. p. 45-60. (Lecture Notes in Artificial Intelligence). doi: 10.1007/978-3-319-08434-3_5

@inbook{f09adb1deeaa4b7eaf448740435425e1,

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, truth table invariance, regular chains, triangular decomposition, problem formulation",

author = "Matthew England and Bradford, {Russell J.} and Changbo Chen and Davenport, {James H.} and {Moreno Maza}, Mark and David Wilson",

year = "2014",

doi = "10.1007/978-3-319-08434-3_5",

language = "English",

isbn = "9783319084336",

series = "Lecture Notes in Artificial Intelligence",

publisher = "Springer",

pages = "45--60",

editor = "Watt, {S. M.} and Davenport, {J. H.} and Sexton, {A. P. } and P. Sojka and J. Urban",

booktitle = "Intelligent Computer Mathematics",

}

TY - CHAP

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

AU - England, Matthew

AU - Bradford, Russell J.

AU - Chen, Changbo

AU - Davenport, James H.

AU - Moreno Maza, Mark

AU - Wilson, David

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 - truth table invariance

KW - regular chains

KW - triangular decomposition

KW - problem formulation

UR - http://dx.doi.org/10.1007/978-3-319-08434-3_5

UR - http://cicm-conference.org/2014/cicm.php

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

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

M3 - Chapter or section

SN - 9783319084336

T3 - Lecture Notes in Artificial Intelligence

SP - 45

EP - 60

BT - Intelligent Computer Mathematics

A2 - Watt, S. M.

A2 - Davenport, J. H.

A2 - Sexton, A. P.

A2 - Sojka, P.

A2 - Urban, J.

PB - Springer

ER -

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

Abstract

Publication series

Keywords

Access to Document

Other files and links

Fingerprint

Real Geometry and Connectedness via Triangular Description

Cite this

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

Abstract

Publication series

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Real Geometry and Connectedness via Triangular Description

Cite this