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

Dorian Florescu; Matthew England

doi:10.1007/978-3-030-52200-1_30

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 proceeding › Conference proceeding › peer-review

7 Citations (Scopus)

50 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 language	English
Title of host publication	Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings
Editors	Anna Maria Bigatti, Jacques Carette, James H. Davenport, Michael Joswig, Timo de Wolff
Publisher	Springer International Publishing
Pages	302-311
Number of pages	10
Volume	(In-Press)
ISBN (Electronic)	978-3-030-52200-1
ISBN (Print)	978-3-030-52199-8
DOIs	https://doi.org/10.1007/978-3-030-52200-1_30
Publication status	Published - 8 Jul 2020
Event	International Congress on Mathematical Software 2020 - Braunschweig, Germany Duration: 13 Jul 2020 → 16 Jul 2020

Publication series

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

Conference

Conference	International Congress on Mathematical Software 2020
Abbreviated title	ICMS 2020
Country/Territory	Germany
City	Braunschweig
Period	13/07/20 → 16/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
General Computer Science

Access to Document

10.1007/978-3-030-52200-1_30

Post-PrintAccepted author manuscript, 498 KBLicence: Unspecified

Cite this

Florescu, D., & England, M. (2020). A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs. In A. M. Bigatti, J. Carette, J. H. Davenport, M. Joswig, & T. de Wolff (Eds.), Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings (Vol. (In-Press), pp. 302-311). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12097 LNCS). Springer International Publishing. https://doi.org/10.1007/978-3-030-52200-1_30

A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs. / Florescu, Dorian; England, Matthew.
Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings. ed. / Anna Maria Bigatti; Jacques Carette; James H. Davenport; Michael Joswig; Timo de Wolff. Vol. (In-Press) Springer International Publishing, 2020. p. 302-311 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12097 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding › peer-review

Florescu, D & England, M 2020, A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs. in AM Bigatti, J Carette, JH Davenport, M Joswig & T de Wolff (eds), Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings. vol. (In-Press), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12097 LNCS, Springer International Publishing, pp. 302-311, International Congress on Mathematical Software 2020, Braunschweig, Germany, 13/07/20. https://doi.org/10.1007/978-3-030-52200-1_30

Florescu D, England M. A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs. In Bigatti AM, Carette J, Davenport JH, Joswig M, de Wolff T, editors, Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings. Vol. (In-Press). Springer International Publishing. 2020. p. 302-311. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-52200-1_30

Florescu, Dorian ; England, Matthew. / A machine learning based software pipeline to pick the variable ordering for algorithms with polynomial inputs. Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings. editor / Anna Maria Bigatti ; Jacques Carette ; James H. Davenport ; Michael Joswig ; Timo de Wolff. Vol. (In-Press) Springer International Publishing, 2020. pp. 302-311 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0738c8c9913944c48d2461632ae05793,

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

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.",

keywords = "Cylindrical algebraic decomposition, Machine learning, Mathematical software, Scikit-learn, Variable ordering",

author = "Dorian Florescu and Matthew England",

note = "The final publication is available at Springer via http://dx.doi.org/ 10.1007/978-3-030-52200-1_30 Copyright {\textcopyright} 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. ; International Congress on Mathematical Software 2020, ICMS 2020 ; Conference date: 13-07-2020 Through 16-07-2020",

year = "2020",

month = jul,

day = "8",

doi = "10.1007/978-3-030-52200-1_30",

language = "English",

isbn = "978-3-030-52199-8",

volume = "(In-Press)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer International Publishing",

pages = "302--311",

editor = "Bigatti, {Anna Maria} and Jacques Carette and Davenport, {James H.} and Michael Joswig and {de Wolff}, Timo",

booktitle = "Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings",

address = "United Kingdom",

}

TY - GEN

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

AU - Florescu, Dorian

AU - England, Matthew

N1 - 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.

PY - 2020/7/8

Y1 - 2020/7/8

N2 - 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.

AB - 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.

KW - Cylindrical algebraic decomposition

KW - Machine learning

KW - Mathematical software

KW - Scikit-learn

KW - Variable ordering

UR - http://www.scopus.com/inward/record.url?scp=85088533780&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-52200-1_30

DO - 10.1007/978-3-030-52200-1_30

M3 - Conference proceeding

SN - 978-3-030-52199-8

VL - (In-Press)

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 302

EP - 311

BT - Mathematical Software – ICMS 2020 - 7th International Conference, Proceedings

A2 - Bigatti, Anna Maria

A2 - Carette, Jacques

A2 - Davenport, James H.

A2 - Joswig, Michael

A2 - de Wolff, Timo

PB - Springer International Publishing

T2 - International Congress on Mathematical Software 2020

Y2 - 13 July 2020 through 16 July 2020

ER -

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

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this