Truth table invariant cylindrical algebraic decomposition by regular chains

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

doi:10.1007/978-3-319-10515-4_4

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 or section in a book/report/conference proceeding › Chapter or section

21 Citations (SciVal)

380 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 language	English
Title of host publication	Computer Algebra in Scientific Computing
Subtitle of host publication	Proceedings of the16th International Workshop, CASC 2014, Warsaw, Poland, September 8-12, 2014
Editors	V. P. Gerdt, W. Koepf, W. M. Seiler, E. V. Vorozhtsov
Publisher	Springer
Pages	44-58
Number of pages	15
Volume	8660
ISBN (Print)	9783319105147
DOIs	https://doi.org/10.1007/978-3-319-10515-4_4
Publication status	Published - 2014

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer

Keywords

cylindrical algebraic decomposition
equational constraint
regular chains
triangular decomposition

Access to Document

10.1007/978-3-319-10515-4_4

BCDEMW14Accepted author manuscript, 598 KB
BCDEMW14-Examples
BCDEMW14-OpusReadMe

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

Truth table invariant cylindrical algebraic decomposition by regular chains. / Bradford, Russell; Chen, Changbo; Davenport, James H. et al.
Computer Algebra in Scientific Computing: Proceedings of the16th International Workshop, CASC 2014, Warsaw, Poland, September 8-12, 2014. ed. / V. P. Gerdt; W. Koepf; W. M. Seiler; E. V. Vorozhtsov. Vol. 8660 Springer, 2014. p. 44-58 (Lecture Notes in Computer Science).

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

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

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

Bradford, Russell ; Chen, Changbo ; Davenport, James H. et al. / Truth table invariant cylindrical algebraic decomposition by regular chains. Computer Algebra in Scientific Computing: Proceedings of the16th International Workshop, CASC 2014, Warsaw, Poland, September 8-12, 2014. editor / V. P. Gerdt ; W. Koepf ; W. M. Seiler ; E. V. Vorozhtsov. Vol. 8660 Springer, 2014. pp. 44-58 (Lecture Notes in Computer Science).

@inbook{a4cee6dd7bf14689ba15f9c44e94fb2b,

title = "Truth table invariant cylindrical algebraic decomposition by regular chains",

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.",

keywords = "cylindrical algebraic decomposition, equational constraint, regular chains, triangular decomposition",

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

year = "2014",

doi = "10.1007/978-3-319-10515-4_4",

language = "English",

isbn = "9783319105147",

volume = "8660",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "44--58",

editor = "Gerdt, {V. P. } and W. Koepf and Seiler, {W. M.} and Vorozhtsov, {E. V.}",

booktitle = "Computer Algebra in Scientific Computing",

}

TY - CHAP

T1 - Truth table invariant cylindrical algebraic decomposition by regular chains

AU - Bradford, Russell

AU - Chen, Changbo

AU - Davenport, James H.

AU - England, Matthew

AU - Moreno Maza, Marc

AU - Wilson, David

PY - 2014

Y1 - 2014

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

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

KW - cylindrical algebraic decomposition

KW - equational constraint

KW - regular chains

KW - triangular decomposition

UR - http://arxiv.org/abs/1401.6310

UR - http://www14.in.tum.de/CASC2014/

UR - http://dx.doi.org/10.1007/978-3-319-10515-4_4

U2 - 10.1007/978-3-319-10515-4_4

DO - 10.1007/978-3-319-10515-4_4

M3 - Chapter or section

SN - 9783319105147

VL - 8660

T3 - Lecture Notes in Computer Science

SP - 44

EP - 58

BT - Computer Algebra in Scientific Computing

A2 - Gerdt, V. P.

A2 - Koepf, W.

A2 - Seiler, W. M.

A2 - Vorozhtsov, E. V.

PB - Springer

ER -

Truth table invariant cylindrical algebraic decomposition by regular chains

Abstract

Publication series

Keywords

Access to Document

Other files and links

Fingerprint

Real Geometry and Connectedness via Triangular Description

Russell Bradford

Cite this

Truth table invariant cylindrical algebraic decomposition by regular chains

Abstract

Publication series

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Real Geometry and Connectedness via Triangular Description

Profiles

Russell Bradford

Cite this