The complexity of cylindrical algebraic decomposition with respect to polynomial degree

Matthew England, James H. Davenport

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

10 Citations (Scopus)
55 Downloads (Pure)

Abstract

Cylindrical algebraic decomposition (CAD) is an important tool for working with polynomial systems, particularly quantifier elimination. However, it has complexity doubly exponential in the number of variables. The base algorithm can be improved by adapting to take advantage of any equational constraints (ECs): equations logically implied by the input. Intuitively, we expect the double exponent in the complexity to decrease by one for each EC. In ISSAC 2015 the present authors proved this for the factor in the complexity bound dependent on the number of polynomials in the input. However, the other term, that dependent on the degree of the input polynomials, remained unchanged.

In the present paper the authors investigate how CAD in the presence of ECs could be further refined using the technology of Groebner Bases to move towards the intuitive bound for polynomial degree.
Original languageEnglish
Title of host publicationComputer Algebra in Scientific Computing
Subtitle of host publication18th International Workshop, CASC 2016, Bucharest, Romania, September 19-23, 2016, Proceedings
EditorsV. P. Gerdt, W. Koepf, W. M. Seiler, E. V. Vorozhtsov
PublisherSpringer Verlag
Pages172-192
Number of pages21
ISBN (Print)9783319456409
DOIs
Publication statusPublished - 9 Sep 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9890
ISSN (Electronic)1611-3349

    Fingerprint

Keywords

  • computer algebra
  • cylindrical algebraic decomposition
  • equational constraint
  • Groebner bases
  • quantifier elimination

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this

England, M., & Davenport, J. H. (2016). The complexity of cylindrical algebraic decomposition with respect to polynomial degree. In V. P. Gerdt, W. Koepf, W. M. Seiler, & E. V. Vorozhtsov (Eds.), Computer Algebra in Scientific Computing: 18th International Workshop, CASC 2016, Bucharest, Romania, September 19-23, 2016, Proceedings (pp. 172-192). (Lecture Notes in Computer Science; Vol. 9890). Springer Verlag. https://doi.org/10.1007/978-3-319-45641-6_12