Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition

2014/04/25 by Zongyan Huang, Matthew England, David Wilson +3 · 4 citations
Computer Science · #cs.SC #cs.LG #msc:68W30 #msc:68T05 #msc:O3C10 #acm:68W30 #acm:68T05 #acm:O3C10

paper · pdf · doi:10.1007/978-3-319-08434-3_8

published as Intelligent Computer Mathematics, pp. 92-107. (Lecture Notes in Artificial Intelligence, 8543). Springer Berlin Heidelberg, 2014 · 16 pages

arxiv created 2014/04/25 · arxiv updated 2014/07/15

Abstract

Cylindrical algebraic decomposition(CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. When using CAD, there is often a choice for the ordering placed on the variables. This can be important, with some problems infeasible with one variable ordering but easy with another. Machine learning is the process of fitting a computer model to a complex function based on properties learned from measured data. In this paper we use machine learning (specifically a support vector machine) to select between heuristics for choosing a variable ordering, outperforming each of the separate heuristics.

Cited by

• Learning Fast Monomial Orders for Gröbner Basis Computations
• Using Machine Learning to Improve Cylindrical Algebraic Decomposition
• Further results on Minimal and Minimum Cylindrical Algebraic Decompositions
• Letting Homogeneity Entropy Select S-Pairs in Buchberger's Algorithm