Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition

Matthew England, Dorian Florescu

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

    13 Citations (Scopus)
    30 Downloads (Pure)

    Abstract

    There has been recent interest in the use of machine learning (ML) approaches within mathematical software to make choices that impact on the computing performance without affecting the mathematical correctness of the result. We address the problem of selecting the variable ordering for cylindrical algebraic decomposition (CAD), an important algorithm in Symbolic Computation. Prior work to apply ML on this problem implemented a Support Vector Machine (SVM) to select between three existing human-made heuristics, which did better than anyone heuristic alone. Here we extend this result by training ML models to select the variable ordering directly, and by trying out a wider variety of ML techniques. We experimented with the NLSAT dataset and the Regular Chains Library CAD function for Maple 2018. For each problem, the variable ordering leading to the shortest computing time was selected as the target class for ML. Features were generated from the polynomial input and used to train the following ML models: k-nearest neighbours (KNN) classifier, multi-layer perceptron (MLP), decision tree (DT) and SVM, as implemented in the Python scikit-learn package. We also compared these with the two leading human-made heuristics for the problem: the Brown heuristic and sotd. On this dataset all of the ML approaches outperformed the human-made heuristics, some by a large margin.

    Original languageEnglish
    Title of host publicationIntelligent Computer Mathematics - 12th International Conference, CICM 2019, Proceedings
    EditorsCezary Kaliszyk, Edwin Brady, Andrea Kohlhase, Claudio Sacerdoti Coen
    PublisherSpringer
    Pages93-108
    Number of pages16
    Volume11617
    ISBN (Electronic)978-3-030-23250-4
    ISBN (Print)978-3-030-23249-8
    DOIs
    Publication statusPublished - 8 Jul 2019
    Event12th Conference on Intelligent Computer Mathematics - Prague, Czech Republic
    Duration: 8 Jul 201912 Jul 2019
    Conference number: 12th
    https://www.cicm-conference.org/2019/cicm.php

    Publication series

    NameLecture Notes in Artificial Intelligence
    PublisherSpringer Verlag
    Volume11617
    ISSN (Electronic)0302-9743

    Conference

    Conference12th Conference on Intelligent Computer Mathematics
    Abbreviated titleCICM 2019
    Country/TerritoryCzech Republic
    CityPrague
    Period8/07/1912/07/19
    Internet address

    Keywords

    • Computer algebra
    • Cylindrical algebraic decomposition
    • Machine learning
    • Non-linear real arithmetic
    • Symbolic computation

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint

    Dive into the research topics of 'Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition'. Together they form a unique fingerprint.

    Cite this