Optimising problem formulation for cylindrical algebraic decomposition

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

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

23 Citations (Scopus)
4 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, a designated equational constraint, and formulations for truth-table invariant CADs (TTICADs). We then consider the possibility of using Gröbner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.

Original languageEnglish
Title of host publicationIntelligent Computer Mathematics - MKM, Calculemus, DML, and Systems and Projects 2013 - Held as Part of CICM 2013, Proceedings
EditorsJacques Carette, David Aspinall, Christoph Lange, Petr Sojka, Wolfgang Windsteiger
Place of PublicationHeidelberg
PublisherSpringer
Pages19-34
Number of pages16
Volume7961 LNAI
ISBN (Electronic)9783642393204
ISBN (Print)9783642393198
DOIs
Publication statusPublished - 2013
Externally publishedYes
EventConference on Intelligent Computer Mathematics, CICM 2013, Co-located with the MKM 2013, Calculemus 2013, DML 2013, and Systems and Projects 2013 - Bath, United Kingdom
Duration: 8 Jul 201312 Jul 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7961 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

ConferenceConference on Intelligent Computer Mathematics, CICM 2013, Co-located with the MKM 2013, Calculemus 2013, DML 2013, and Systems and Projects 2013
CountryUnited Kingdom
CityBath
Period8/07/1312/07/13

Fingerprint

Truth table
Decomposition
Decompose
Formulation
Computer aided design
Real Algebraic Geometry
Problem Decomposition
Invariant
Geometry
Tractability
Precondition
Vary
Heuristics

Keywords

  • cylindrical algebraic decomposition
  • Gröbner bases
  • problem formulation
  • symbolic computation

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

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, Proceedings (Vol. 7961 LNAI, pp. 19-34). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7961 LNAI). Heidelberg: 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; Wilson, David.

Intelligent Computer Mathematics - MKM, Calculemus, DML, and Systems and Projects 2013 - Held as Part of CICM 2013, Proceedings. ed. / Jacques Carette; David Aspinall; Christoph Lange; Petr Sojka; Wolfgang Windsteiger. Vol. 7961 LNAI Heidelberg : Springer, 2013. p. 19-34 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7961 LNAI).

Research output: Chapter in Book/Report/Conference proceedingConference 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, Proceedings. vol. 7961 LNAI, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7961 LNAI, Springer, Heidelberg, pp. 19-34, Conference on Intelligent Computer Mathematics, CICM 2013, Co-located with the MKM 2013, Calculemus 2013, DML 2013, and Systems and Projects 2013, Bath, United Kingdom, 8/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, Proceedings. Vol. 7961 LNAI. Heidelberg: Springer. 2013. p. 19-34. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-39320-4_2
Bradford, Russell ; Davenport, James H. ; England, Matthew ; Wilson, David. / Optimising problem formulation for cylindrical algebraic decomposition. Intelligent Computer Mathematics - MKM, Calculemus, DML, and Systems and Projects 2013 - Held as Part of CICM 2013, Proceedings. editor / Jacques Carette ; David Aspinall ; Christoph Lange ; Petr Sojka ; Wolfgang Windsteiger. Vol. 7961 LNAI Heidelberg : Springer, 2013. pp. 19-34 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{c22f16cefb6a40b98a8e186473aa328c,
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, a designated equational constraint, and formulations for truth-table invariant CADs (TTICADs). We then consider the possibility of using Gr{\"o}bner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.",
keywords = "cylindrical algebraic decomposition, Gr{\"o}bner bases, problem formulation, symbolic computation",
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",
volume = "7961 LNAI",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "19--34",
editor = "Jacques Carette and David Aspinall and Christoph Lange and Petr Sojka and Wolfgang Windsteiger",
booktitle = "Intelligent Computer Mathematics - MKM, Calculemus, DML, and Systems and Projects 2013 - Held as Part of CICM 2013, Proceedings",

}

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, a designated equational constraint, and formulations for truth-table invariant CADs (TTICADs). We then consider the possibility of using Gröbner 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, a designated equational constraint, and formulations for truth-table invariant CADs (TTICADs). We then consider the possibility of using Gröbner bases to precondition TTICAD and when such formulations constitute the creation of a new problem.

KW - cylindrical algebraic decomposition

KW - Gröbner bases

KW - problem formulation

KW - symbolic computation

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

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

M3 - Conference proceeding

SN - 9783642393198

VL - 7961 LNAI

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

SP - 19

EP - 34

BT - Intelligent Computer Mathematics - MKM, Calculemus, DML, and Systems and Projects 2013 - Held as Part of CICM 2013, Proceedings

A2 - Carette, Jacques

A2 - Aspinall, David

A2 - Lange, Christoph

A2 - Sojka, Petr

A2 - Windsteiger, Wolfgang

PB - Springer

CY - Heidelberg

ER -