The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree

Matthew England, James H. Davenport

    Research output: Chapter in Book/Report/Conference proceedingConference proceedingpeer-review

    18 Citations (Scopus)
    119 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 Gr¨obner Bases to move towards the intuitive bound for polynomial degree.
    Original languageEnglish
    Title of host publicationComputer Algebra in Scientific Computing
    EditorsVladimir P. Gerdt, Wolfram Koepf, Werner M. Seiler, Evgenii V. Vorozhtsov
    Place of PublicationSwitzerland
    PublisherSpringer Verlag
    Pages172-192
    Number of pages21
    ISBN (Electronic)978-3-319-45641-6
    ISBN (Print)978-3-319-45640-9
    DOIs
    Publication statusPublished - 9 Sept 2016
    EventInternational Workshop on Computer Algebra in Scientific Computing - Bucharest, Romania
    Duration: 19 Sept 201623 Sept 2016

    Publication series

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

    Workshop

    WorkshopInternational Workshop on Computer Algebra in Scientific Computing
    Country/TerritoryRomania
    CityBucharest
    Period19/09/1623/09/16

    Bibliographical note

    The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-45641-6_12

    Copyright © and Moral Rights are retained by the author(s) and/ or other copyright owners. A copy can be downloaded for personal non-commercial research or study, without prior permission or charge. This item cannot be reproduced or quoted extensively from without first obtaining permission in writing from the copyright holder(s). The content must not be changed in any way or sold commercially in any format or medium without the formal permission of the copyright holders.

    Lecture Notes in Computer Science ISSN 0302-9743

    Fingerprint

    Dive into the research topics of 'The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree'. Together they form a unique fingerprint.

    Cite this