Optimising problem formulation for cylindrical algebraic decomposition

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

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

27 Citations (Scopus)
122 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 languageEnglish
Title of host publicationIntelligent Computer Mathematics
Subtitle of host publicationMKM, Calculemus, DML, and Systems and Projects 2013, Held as Part of CICM 2013, Bath, UK, July 8-12, 2013. Proceedings
EditorsJacques Carette, David Aspinall, Christoph Lange, Petr Sojka, Wolfgang Windsteiger
Place of PublicationBerlin
PublisherSpringer
Pages19-34
Number of pages15
ISBN (Electronic)9783642393204
ISBN (Print)9783642393198
DOIs
Publication statusPublished - 2013
EventConferences on Intelligent Computer Mathematics: CICM 2013 - Bath, UK United Kingdom
Duration: 7 Jul 201311 Jul 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7961
ISSN (Print)0302-9743

Conference

ConferenceConferences on Intelligent Computer Mathematics: CICM 2013
CountryUK United Kingdom
CityBath
Period7/07/1311/07/13

Keywords

  • cylindrical algebraic decomposition
  • Groebner bases
  • problem formulation
  • symbolic computation
  • equational constraint

Fingerprint Dive into the research topics of 'Optimising problem formulation for cylindrical algebraic decomposition'. Together they form a unique fingerprint.

  • Projects

  • 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