Exploring Alternative Machine Learning Models for Variable Ordering in Cylindrical Algebraic Decomposition

Rohit John; James Davenport

doi:10.1007/978-3-031-64529-7_20

Exploring Alternative Machine Learning Models for Variable Ordering in Cylindrical Algebraic Decomposition

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

Abstract

Cylindrical Algebraic Decomposition is a computer algebra tool with many applications, from robotics to biochemistry. But it can be very sensitive to the ordering of the variables, which may be partially prescribed by the problem, but generally has at least some freedom. While various algorithmic heuristics to choose the best variable order exist, we are looking at using new machine learning models to pick the variable order directly. Of those machine learning methods we have currently implemented, Feed-forward networks seem the most successful (though some others are nearly as good), and much better than a traditional hand crafted heuristic such as Brown’s. We also explore an implementation of Graph Neural Networks as well as possible data pollution in current CAD datasets.

Original language	English
Title of host publication	Mathematical Software – ICMS 2024 - 8th International Conference, Proceedings
Editors	Kevin Buzzard, Alicia Dickenstein, Bettina Eick, Anton Leykin, Yue Ren
Place of Publication	Cham, Switzerland
Publisher	Springer, Cham
Pages	176-185
Number of pages	10
ISBN (Print)	9783031645280
DOIs	https://doi.org/10.1007/978-3-031-64529-7_20
Publication status	Published - 17 Jul 2024
Event	8th International Conference on Mathematical Software, ICMS 2024 - Durham, UK United Kingdom Duration: 22 Jul 2024 → 25 Jul 2024

Publication series

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

Conference

Conference	8th International Conference on Mathematical Software, ICMS 2024
Country/Territory	UK United Kingdom
City	Durham
Period	22/07/24 → 25/07/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

Funding

Davenport was partially funded by the UK\u2019s EPSRC under grant EP/T015748/1. We are grateful to Matthew England and Tereso del R\u00EDo (Coventry University) for useful comments, as well as Yuhang Dong and Fuqi Jia for access to their dataset. We are grateful to the referees for many comments and drawing our attention to [13].

Funders	Funder number
Coventry University
Engineering and Physical Sciences Research Council	EP/T015748/1

Keywords

Computer Algebra
Cylindrical Algebraic Decomposition
Machine Learning
Variable Ordering

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-64529-7_20

Cite this

John, R., & Davenport, J. (2024). Exploring Alternative Machine Learning Models for Variable Ordering in Cylindrical Algebraic Decomposition. In K. Buzzard, A. Dickenstein, B. Eick, A. Leykin, & Y. Ren (Eds.), Mathematical Software – ICMS 2024 - 8th International Conference, Proceedings (pp. 176-185). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14749 LNCS). Springer, Cham. https://doi.org/10.1007/978-3-031-64529-7_20

Exploring Alternative Machine Learning Models for Variable Ordering in Cylindrical Algebraic Decomposition. / John, Rohit; Davenport, James.
Mathematical Software – ICMS 2024 - 8th International Conference, Proceedings. ed. / Kevin Buzzard; Alicia Dickenstein; Bettina Eick; Anton Leykin; Yue Ren. Cham, Switzerland: Springer, Cham, 2024. p. 176-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14749 LNCS).

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

John, R & Davenport, J 2024, Exploring Alternative Machine Learning Models for Variable Ordering in Cylindrical Algebraic Decomposition. in K Buzzard, A Dickenstein, B Eick, A Leykin & Y Ren (eds), Mathematical Software – ICMS 2024 - 8th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14749 LNCS, Springer, Cham, Cham, Switzerland, pp. 176-185, 8th International Conference on Mathematical Software, ICMS 2024, Durham, UK United Kingdom, 22/07/24. https://doi.org/10.1007/978-3-031-64529-7_20

John R, Davenport J. Exploring Alternative Machine Learning Models for Variable Ordering in Cylindrical Algebraic Decomposition. In Buzzard K, Dickenstein A, Eick B, Leykin A, Ren Y, editors, Mathematical Software – ICMS 2024 - 8th International Conference, Proceedings. Cham, Switzerland: Springer, Cham. 2024. p. 176-185. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-64529-7_20

John, Rohit ; Davenport, James. / Exploring Alternative Machine Learning Models for Variable Ordering in Cylindrical Algebraic Decomposition. Mathematical Software – ICMS 2024 - 8th International Conference, Proceedings. editor / Kevin Buzzard ; Alicia Dickenstein ; Bettina Eick ; Anton Leykin ; Yue Ren. Cham, Switzerland : Springer, Cham, 2024. pp. 176-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6a29354c6ff7472eb897cee9c6f1b487,

title = "Exploring Alternative Machine Learning Models for Variable Ordering in Cylindrical Algebraic Decomposition",

abstract = "Cylindrical Algebraic Decomposition is a computer algebra tool with many applications, from robotics to biochemistry. But it can be very sensitive to the ordering of the variables, which may be partially prescribed by the problem, but generally has at least some freedom. While various algorithmic heuristics to choose the best variable order exist, we are looking at using new machine learning models to pick the variable order directly. Of those machine learning methods we have currently implemented, Feed-forward networks seem the most successful (though some others are nearly as good), and much better than a traditional hand crafted heuristic such as Brown{\textquoteright}s. We also explore an implementation of Graph Neural Networks as well as possible data pollution in current CAD datasets.",

keywords = "Computer Algebra, Cylindrical Algebraic Decomposition, Machine Learning, Variable Ordering",

author = "Rohit John and James Davenport",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 8th International Conference on Mathematical Software, ICMS 2024 ; Conference date: 22-07-2024 Through 25-07-2024",

year = "2024",

month = jul,

day = "17",

doi = "10.1007/978-3-031-64529-7_20",

language = "English",

isbn = "9783031645280",

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

publisher = "Springer, Cham",

pages = "176--185",

editor = "Kevin Buzzard and Alicia Dickenstein and Bettina Eick and Anton Leykin and Yue Ren",

booktitle = "Mathematical Software – ICMS 2024 - 8th International Conference, Proceedings",

}

TY - GEN

T1 - Exploring Alternative Machine Learning Models for Variable Ordering in Cylindrical Algebraic Decomposition

AU - John, Rohit

AU - Davenport, James

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

PY - 2024/7/17

Y1 - 2024/7/17

N2 - Cylindrical Algebraic Decomposition is a computer algebra tool with many applications, from robotics to biochemistry. But it can be very sensitive to the ordering of the variables, which may be partially prescribed by the problem, but generally has at least some freedom. While various algorithmic heuristics to choose the best variable order exist, we are looking at using new machine learning models to pick the variable order directly. Of those machine learning methods we have currently implemented, Feed-forward networks seem the most successful (though some others are nearly as good), and much better than a traditional hand crafted heuristic such as Brown’s. We also explore an implementation of Graph Neural Networks as well as possible data pollution in current CAD datasets.

AB - Cylindrical Algebraic Decomposition is a computer algebra tool with many applications, from robotics to biochemistry. But it can be very sensitive to the ordering of the variables, which may be partially prescribed by the problem, but generally has at least some freedom. While various algorithmic heuristics to choose the best variable order exist, we are looking at using new machine learning models to pick the variable order directly. Of those machine learning methods we have currently implemented, Feed-forward networks seem the most successful (though some others are nearly as good), and much better than a traditional hand crafted heuristic such as Brown’s. We also explore an implementation of Graph Neural Networks as well as possible data pollution in current CAD datasets.

KW - Computer Algebra

KW - Cylindrical Algebraic Decomposition

KW - Machine Learning

KW - Variable Ordering

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

U2 - 10.1007/978-3-031-64529-7_20

DO - 10.1007/978-3-031-64529-7_20

M3 - Chapter in a published conference proceeding

AN - SCOPUS:85200672547

SN - 9783031645280

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

SP - 176

EP - 185

BT - Mathematical Software – ICMS 2024 - 8th International Conference, Proceedings

A2 - Buzzard, Kevin

A2 - Dickenstein, Alicia

A2 - Eick, Bettina

A2 - Leykin, Anton

A2 - Ren, Yue

PB - Springer, Cham

CY - Cham, Switzerland

T2 - 8th International Conference on Mathematical Software, ICMS 2024

Y2 - 22 July 2024 through 25 July 2024

ER -