Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases

Z. Huang, Matthew England, J. H. Davenport, L. C. Paulson

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

    15 Citations (Scopus)
    69 Downloads (Pure)

    Abstract

    Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. However, it can be expensive, with worst case complexity doubly exponential in the size of the input. Hence it is important to formulate the problem in the best manner for the CAD algorithm. One possibility is to precondition the input polynomials using Groebner Basis (GB) theory. Previous experiments have shown that while this can often be very beneficial to the CAD algorithm, for some problems it can significantly worsen the CAD performance. In the present paper we investigate whether machine learning, specifically a support vector machine (SVM), may be used to identify those CAD problems which benefit from GB preconditioning. We run experiments with over 1000 problems (many times larger than previous studies) and find that the machine learned choice does better than the human-made heuristic.
    Original languageEnglish
    Title of host publication18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
    Place of PublicationCalifornia
    PublisherIEEE Computer Society
    Pages45-52
    ISBN (Print) 978-1-5090-5707-8
    DOIs
    Publication statusPublished - 26 Jan 2017
    EventInternational Symposium on Symbolic and Numeric Algorithms for Scientific Computing - Timisoara, Romania
    Duration: 24 Sept 201627 Sept 2016

    Conference

    ConferenceInternational Symposium on Symbolic and Numeric Algorithms for Scientific Computing
    Country/TerritoryRomania
    CityTimisoara
    Period24/09/1627/09/16

    Bibliographical note

    © 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. ISSN 2470-881X

    Keywords

    • preconditioning
    • machine learning
    • support vector machine
    • computer algebra
    • cylindrical algebraic decomposition
    • groebner bases
    • Computers
    • Algebra
    • Machine learning algorithms
    • Support vector machines
    • Measurement
    • Electronic mail
    • Complexity theory

    Fingerprint

    Dive into the research topics of 'Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases'. Together they form a unique fingerprint.

    Cite this