Optimising problem formulation for cylindrical algebraic decomposition

Russell Bradford; James H Davenport; Matthew England; David Wilson

doi:10.1007/978-3-642-39320-4_2

Optimising problem formulation for cylindrical algebraic decomposition

Russell Bradford, James H Davenport, Matthew England, David Wilson

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

38 Citations (SciVal)

187 Downloads (Pure)

Abstract

Cylindrical algebraic decomposition (CAD) is an important tool for the study of real algebraic geometry with many applications both within mathematics and elsewhere. It is known to have doubly exponential complexity in the number of variables in the worst case, but the actual computation time can vary greatly. It is possible to offer different formulations for a given problem leading to great differences in tractability. In this paper we suggest a new measure for CAD complexity which takes into account the real geometry of the problem. This leads to new heuristics for choosing the variable ordering for a CAD problem, choosing a designated equational constraint and choosing clause formulation for truth-table invariant CADs (TTICADs). We then consider the possibility of using Groebner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.

Original language	English
Title of host publication	Intelligent Computer Mathematics
Subtitle of host publication	MKM, Calculemus, DML, and Systems and Projects 2013, Held as Part of CICM 2013, Bath, UK, July 8-12, 2013. Proceedings
Editors	Jacques Carette, David Aspinall, Christoph Lange, Petr Sojka, Wolfgang Windsteiger
Place of Publication	Berlin
Publisher	Springer
Pages	19-34
Number of pages	15
ISBN (Electronic)	9783642393204
ISBN (Print)	9783642393198
DOIs	https://doi.org/10.1007/978-3-642-39320-4_2
Publication status	Published - 2013
Event	Conferences on Intelligent Computer Mathematics: CICM 2013 - Bath, UK United Kingdom Duration: 7 Jul 2013 → 11 Jul 2013

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	7961
ISSN (Print)	0302-9743

Conference

Conference	Conferences on Intelligent Computer Mathematics: CICM 2013
Country/Territory	UK United Kingdom
City	Bath
Period	7/07/13 → 11/07/13

Keywords

cylindrical algebraic decomposition
Groebner bases
problem formulation
symbolic computation
equational constraint

Access to Document

10.1007/978-3-642-39320-4_2

Author's accepted version
The final publication is available at link.springer.com
Accepted author manuscript, 505 KB

Cite this

Bradford, R., Davenport, J. H., England, M., & Wilson, D. (2013). Optimising problem formulation for cylindrical algebraic decomposition. In J. Carette, D. Aspinall, C. Lange, P. Sojka, & W. Windsteiger (Eds.), Intelligent Computer Mathematics: MKM, Calculemus, DML, and Systems and Projects 2013, Held as Part of CICM 2013, Bath, UK, July 8-12, 2013. Proceedings (pp. 19-34). (Lecture Notes in Computer Science; Vol. 7961). Springer. https://doi.org/10.1007/978-3-642-39320-4_2

Optimising problem formulation for cylindrical algebraic decomposition. / Bradford, Russell; Davenport, James H; England, Matthew et al.
Intelligent Computer Mathematics: MKM, Calculemus, DML, and Systems and Projects 2013, Held as Part of CICM 2013, Bath, UK, July 8-12, 2013. Proceedings. ed. / Jacques Carette; David Aspinall; Christoph Lange; Petr Sojka; Wolfgang Windsteiger. Berlin: Springer, 2013. p. 19-34 (Lecture Notes in Computer Science; Vol. 7961).

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

Bradford, R, Davenport, JH, England, M & Wilson, D 2013, Optimising problem formulation for cylindrical algebraic decomposition. in J Carette, D Aspinall, C Lange, P Sojka & W Windsteiger (eds), Intelligent Computer Mathematics: MKM, Calculemus, DML, and Systems and Projects 2013, Held as Part of CICM 2013, Bath, UK, July 8-12, 2013. Proceedings. Lecture Notes in Computer Science, vol. 7961, Springer, Berlin, pp. 19-34, Conferences on Intelligent Computer Mathematics: CICM 2013, Bath, UK United Kingdom, 7/07/13. https://doi.org/10.1007/978-3-642-39320-4_2

Bradford R, Davenport JH, England M, Wilson D. Optimising problem formulation for cylindrical algebraic decomposition. In Carette J, Aspinall D, Lange C, Sojka P, Windsteiger W, editors, Intelligent Computer Mathematics: MKM, Calculemus, DML, and Systems and Projects 2013, Held as Part of CICM 2013, Bath, UK, July 8-12, 2013. Proceedings. Berlin: Springer. 2013. p. 19-34. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-39320-4_2

Bradford, Russell ; Davenport, James H ; England, Matthew et al. / Optimising problem formulation for cylindrical algebraic decomposition. Intelligent Computer Mathematics: MKM, Calculemus, DML, and Systems and Projects 2013, Held as Part of CICM 2013, Bath, UK, July 8-12, 2013. Proceedings. editor / Jacques Carette ; David Aspinall ; Christoph Lange ; Petr Sojka ; Wolfgang Windsteiger. Berlin : Springer, 2013. pp. 19-34 (Lecture Notes in Computer Science).

@inproceedings{6a98aa34c71445d998a7b759f220cd2d,

title = "Optimising problem formulation for cylindrical algebraic decomposition",

abstract = "Cylindrical algebraic decomposition (CAD) is an important tool for the study of real algebraic geometry with many applications both within mathematics and elsewhere. It is known to have doubly exponential complexity in the number of variables in the worst case, but the actual computation time can vary greatly. It is possible to offer different formulations for a given problem leading to great differences in tractability. In this paper we suggest a new measure for CAD complexity which takes into account the real geometry of the problem. This leads to new heuristics for choosing the variable ordering for a CAD problem, choosing a designated equational constraint and choosing clause formulation for truth-table invariant CADs (TTICADs). We then consider the possibility of using Groebner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.",

keywords = "cylindrical algebraic decomposition, Groebner bases, problem formulation, symbolic computation, equational constraint",

author = "Russell Bradford and Davenport, {James H} and Matthew England and David Wilson",

year = "2013",

doi = "10.1007/978-3-642-39320-4_2",

language = "English",

isbn = "9783642393198",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "19--34",

editor = "Jacques Carette and David Aspinall and Christoph Lange and Petr Sojka and Wolfgang Windsteiger",

booktitle = "Intelligent Computer Mathematics",

note = "Conferences on Intelligent Computer Mathematics: CICM 2013 ; Conference date: 07-07-2013 Through 11-07-2013",

}

TY - GEN

T1 - Optimising problem formulation for cylindrical algebraic decomposition

AU - Bradford, Russell

AU - Davenport, James H

AU - England, Matthew

AU - Wilson, David

PY - 2013

Y1 - 2013

N2 - Cylindrical algebraic decomposition (CAD) is an important tool for the study of real algebraic geometry with many applications both within mathematics and elsewhere. It is known to have doubly exponential complexity in the number of variables in the worst case, but the actual computation time can vary greatly. It is possible to offer different formulations for a given problem leading to great differences in tractability. In this paper we suggest a new measure for CAD complexity which takes into account the real geometry of the problem. This leads to new heuristics for choosing the variable ordering for a CAD problem, choosing a designated equational constraint and choosing clause formulation for truth-table invariant CADs (TTICADs). We then consider the possibility of using Groebner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.

AB - Cylindrical algebraic decomposition (CAD) is an important tool for the study of real algebraic geometry with many applications both within mathematics and elsewhere. It is known to have doubly exponential complexity in the number of variables in the worst case, but the actual computation time can vary greatly. It is possible to offer different formulations for a given problem leading to great differences in tractability. In this paper we suggest a new measure for CAD complexity which takes into account the real geometry of the problem. This leads to new heuristics for choosing the variable ordering for a CAD problem, choosing a designated equational constraint and choosing clause formulation for truth-table invariant CADs (TTICADs). We then consider the possibility of using Groebner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.

KW - cylindrical algebraic decomposition

KW - Groebner bases

KW - problem formulation

KW - symbolic computation

KW - equational constraint

UR - http://www.scopus.com/inward/record.url?scp=84880711618&partnerID=8YFLogxK

UR - http://www.cicm-conference.org/2013/

UR - http://dx.doi.org/10.1007/978-3-642-39320-4_2

U2 - 10.1007/978-3-642-39320-4_2

DO - 10.1007/978-3-642-39320-4_2

M3 - Chapter in a published conference proceeding

AN - SCOPUS:84880711618

SN - 9783642393198

T3 - Lecture Notes in Computer Science

SP - 19

EP - 34

BT - Intelligent Computer Mathematics

A2 - Carette, Jacques

A2 - Aspinall, David

A2 - Lange, Christoph

A2 - Sojka, Petr

A2 - Windsteiger, Wolfgang

PB - Springer

CY - Berlin

T2 - Conferences on Intelligent Computer Mathematics: CICM 2013

Y2 - 7 July 2013 through 11 July 2013

ER -

Optimising problem formulation for cylindrical algebraic decomposition

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Real Geometry and Connectedness via Triangular Description

Cite this