Improving the use of equational constraints in cylindrical algebraic decomposition

Matthew England, R. Bradford, J.H. Davenport

    Research output: Contribution to conferencePaperpeer-review

    25 Citations (Scopus)
    49 Downloads (Pure)

    Abstract

    When building a cylindrical algebraic decomposition (CAD) savings can be made in the presence of an equational constraint (EC): an equation logically implied by a formula. The present paper is concerned with how to use multiple ECs, propagating those in the input throughout the projection set. We improve on the approach of McCallum in ISSAC 2001 by using the reduced projection theory to make savings in the lifting phase (both to the polynomials we lift with and the cells lifted over). We demonstrate the benefits with worked examples and a complexity analysis.
    Original languageEnglish
    Pages165-172
    DOIs
    Publication statusPublished - 2015
    Event40th International Symposium on Symbolic and Algebraic Computation (ISSAC) - The University of Bath, Bath, United Kingdom
    Duration: 6 Jul 20159 Jul 2015

    Conference

    Conference40th International Symposium on Symbolic and Algebraic Computation (ISSAC)
    Country/TerritoryUnited Kingdom
    CityBath
    Period6/07/159/07/15

    Keywords

    • cylindrical algebraic decomposition
    • equational constraint

    Fingerprint

    Dive into the research topics of 'Improving the use of equational constraints in cylindrical algebraic decomposition'. Together they form a unique fingerprint.

    Cite this