### Abstract

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 constructed heuristics for the problem: Brown's heuristic and sotd. On this dataset all of the ML approaches outperformed the human made heuristics, some by a large margin.

Language | English |
---|---|

Title of host publication | Intelligent Computer Mathematics (Proc. CICM 2019) |

Pages | (In-press) |

Number of pages | 16 |

Volume | 11617 |

Publication status | Accepted/In press - 24 Apr 2019 |

Event | 12th Conference on Intelligent Computer Mathematics - Prague, Czech Republic Duration: 8 Jul 2019 → 12 Jul 2019 Conference number: 12th https://www.cicm-conference.org/2019/cicm.php |

### Publication series

Name | Lecture Notes in Artificial Intelligence |
---|

### Conference

Conference | 12th Conference on Intelligent Computer Mathematics |
---|---|

Abbreviated title | CICM 2019 |

Country | Czech Republic |

City | Prague |

Period | 8/07/19 → 12/07/19 |

Internet address |

### Fingerprint

### Keywords

- computer algebra
- symbolic computation
- non-linear real arithmetic
- cylindrical algebraic decomposition
- machine learning

### Cite this

*Intelligent Computer Mathematics (Proc. CICM 2019)*(Vol. 11617, pp. (In-press)). (Lecture Notes in Artificial Intelligence).

**Comparing machine learning models to choose the variable ordering for cylindrical algebraic decomposition.** / England, Matthew; Florescu, Dorian.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding

*Intelligent Computer Mathematics (Proc. CICM 2019).*vol. 11617, Lecture Notes in Artificial Intelligence, pp. (In-press), 12th Conference on Intelligent Computer Mathematics, Prague, Czech Republic, 8/07/19.

}

TY - GEN

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

AU - England, Matthew

AU - Florescu, Dorian

PY - 2019/4/24

Y1 - 2019/4/24

N2 - 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. The present work extends to have ML select the variable ordering directly, and to try 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 constructed heuristics for the problem: Brown's heuristic and sotd. On this dataset all of the ML approaches outperformed the human made heuristics, some by a large margin.

AB - 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. The present work extends to have ML select the variable ordering directly, and to try 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 constructed heuristics for the problem: Brown's heuristic and sotd. On this dataset all of the ML approaches outperformed the human made heuristics, some by a large margin.

KW - computer algebra

KW - symbolic computation

KW - non-linear real arithmetic

KW - cylindrical algebraic decomposition

KW - machine learning

M3 - Conference proceeding

VL - 11617

T3 - Lecture Notes in Artificial Intelligence

SP - (In-press)

BT - Intelligent Computer Mathematics (Proc. CICM 2019)

ER -