A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs

Dorian Florescu, Matthew England

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

    4 Downloads (Pure)

    Abstract

    We are interested in the application of Machine Learning (ML) technology to improve mathematical software. It may seem that the probabilistic nature of ML tools would invalidate the exact results prized by such software, however, the algorithms which underpin the software often come with a range of choices which are good candidates for ML application. We refer to choices which have no effect on the mathematical correctness of the software, but do impact its performance.

    In the past we experimented with one such choice: the variable ordering to use when building a Cylindrical Algebraic Decomposition (CAD). We used the Python library Scikit-Learn (sklearn) to experiment with different ML models, and developed new techniques for feature generation and hyper-parameter selection.


    These techniques could easily be adapted for making decisions other than our immediate application of CAD variable ordering. Hence in this paper we present a software pipeline to use sklearn to pick the variable ordering for an algorithm that acts on a polynomial system. The code described is freely available online.
    Original languageEnglish
    Title of host publicationMathematical Software – ICMS 2020 - 7th International Conference, Proceedings
    EditorsAnna Maria Bigatti, Jacques Carette, James H. Davenport, Michael Joswig, Timo de Wolff
    PublisherSpringer International Publishing
    Pages302-311
    Number of pages10
    Volume(In-Press)
    ISBN (Electronic)978-3-030-52200-1
    ISBN (Print)978-3-030-52199-8
    DOIs
    Publication statusPublished - 8 Jul 2020
    EventInternational Congress on Mathematical Software 2020 - Braunschweig, Germany
    Duration: 13 Jul 202016 Jul 2020

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume12097 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    ConferenceInternational Congress on Mathematical Software 2020
    Abbreviated titleICMS 2020
    CountryGermany
    CityBraunschweig
    Period13/07/2016/07/20

    Bibliographical note

    The final publication is available at Springer via http://dx.doi.org/ 10.1007/978-3-030-52200-1_30

    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.

    Keywords

    • Cylindrical algebraic decomposition
    • Machine learning
    • Mathematical software
    • Scikit-learn
    • Variable ordering

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint

    Dive into the research topics of 'A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs'. Together they form a unique fingerprint.

    Cite this