Using Machine Learning to Improve Cylindrical Algebraic Decomposition

Zongyan Huang, Matthew England, David Wilson, James Bridge, James H. Davenport, Lawrence C. Paulson

Research output: Contribution to journalArticle

3 Downloads (Pure)

Abstract

Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, best known as a procedure to enable Quantifier Elimination over real-closed fields. However, it has a worst case complexity doubly exponential in the size of the input, which is often encountered in practice. It has been observed that for many problems a change in algorithm settings or problem formulation can cause huge differences in runtime costs, changing problem instances from intractable to easy. A number of heuristics have been developed to help with such choices, but the complicated nature of the geometric relationships involved means these are imperfect and can sometimes make poor choices. We investigate the use of machine learning (specifically support vector machines) to make such choices instead.

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 apply it in two case studies: the first to select between heuristics for choosing a CAD variable ordering; the second to identify when a CAD problem instance would benefit from Groebner Basis preconditioning. These appear to be the first such applications of machine learning to Symbolic Computation. We demonstrate in both cases that the machine learned choice outperforms human developed heuristics.
Original languageEnglish
Pages (from-to)(In-Press)
Number of pages28
JournalMathematics in Computer Science
Volume(In-Press)
Early online date3 Apr 2019
DOIs
Publication statusE-pub ahead of print - 3 Apr 2019

Fingerprint

Learning systems
Machine Learning
Heuristics
Decomposition
Decompose
Groebner Basis
Real Closed Fields
Computational geometry
Problem Decomposition
Quantifier Elimination
Algebraic Geometry
Computational Geometry
Symbolic Computation
Complex Functions
Computer Model
Preconditioning
Imperfect
Support vector machines
Support Vector Machine
Formulation

Bibliographical note

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Keywords

  • Symbolic computation
  • Machine Learning
  • Cylindrical algebraic decomposition
  • Support Vector Machine
  • Computer Algebra
  • Grobner Basis
  • Parameter Selection

Cite this

Huang, Z., England, M., Wilson, D., Bridge, J., Davenport, J. H., & Paulson, L. C. (2019). Using Machine Learning to Improve Cylindrical Algebraic Decomposition. Mathematics in Computer Science, (In-Press), (In-Press). https://doi.org/10.1007/s11786-019-00394-8

Using Machine Learning to Improve Cylindrical Algebraic Decomposition. / Huang, Zongyan; England, Matthew; Wilson, David; Bridge, James; Davenport, James H.; Paulson, Lawrence C.

In: Mathematics in Computer Science, Vol. (In-Press), 03.04.2019, p. (In-Press).

Research output: Contribution to journalArticle

Huang, Z, England, M, Wilson, D, Bridge, J, Davenport, JH & Paulson, LC 2019, 'Using Machine Learning to Improve Cylindrical Algebraic Decomposition' Mathematics in Computer Science, vol. (In-Press), pp. (In-Press). https://doi.org/10.1007/s11786-019-00394-8
Huang, Zongyan ; England, Matthew ; Wilson, David ; Bridge, James ; Davenport, James H. ; Paulson, Lawrence C. / Using Machine Learning to Improve Cylindrical Algebraic Decomposition. In: Mathematics in Computer Science. 2019 ; Vol. (In-Press). pp. (In-Press).
@article{52c17e8fdf154a29a75a4436336c927b,
title = "Using Machine Learning to Improve Cylindrical Algebraic Decomposition",
abstract = "Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, best known as a procedure to enable Quantifier Elimination over real-closed fields. However, it has a worst case complexity doubly exponential in the size of the input, which is often encountered in practice. It has been observed that for many problems a change in algorithm settings or problem formulation can cause huge differences in runtime costs, changing problem instances from intractable to easy. A number of heuristics have been developed to help with such choices, but the complicated nature of the geometric relationships involved means these are imperfect and can sometimes make poor choices. We investigate the use of machine learning (specifically support vector machines) to make such choices instead. 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 apply it in two case studies: the first to select between heuristics for choosing a CAD variable ordering; the second to identify when a CAD problem instance would benefit from Groebner Basis preconditioning. These appear to be the first such applications of machine learning to Symbolic Computation. We demonstrate in both cases that the machine learned choice outperforms human developed heuristics.",
keywords = "Symbolic computation, Machine Learning, Cylindrical algebraic decomposition, Support Vector Machine, Computer Algebra, Grobner Basis, Parameter Selection",
author = "Zongyan Huang and Matthew England and David Wilson and James Bridge and Davenport, {James H.} and Paulson, {Lawrence C.}",
note = "This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.",
year = "2019",
month = "4",
day = "3",
doi = "10.1007/s11786-019-00394-8",
language = "English",
volume = "(In-Press)",
pages = "(In--Press)",
journal = "Mathematics in Computer Science",
issn = "1661-8270",
publisher = "Springer Verlag",

}

TY - JOUR

T1 - Using Machine Learning to Improve Cylindrical Algebraic Decomposition

AU - Huang, Zongyan

AU - England, Matthew

AU - Wilson, David

AU - Bridge, James

AU - Davenport, James H.

AU - Paulson, Lawrence C.

N1 - This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

PY - 2019/4/3

Y1 - 2019/4/3

N2 - Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, best known as a procedure to enable Quantifier Elimination over real-closed fields. However, it has a worst case complexity doubly exponential in the size of the input, which is often encountered in practice. It has been observed that for many problems a change in algorithm settings or problem formulation can cause huge differences in runtime costs, changing problem instances from intractable to easy. A number of heuristics have been developed to help with such choices, but the complicated nature of the geometric relationships involved means these are imperfect and can sometimes make poor choices. We investigate the use of machine learning (specifically support vector machines) to make such choices instead. 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 apply it in two case studies: the first to select between heuristics for choosing a CAD variable ordering; the second to identify when a CAD problem instance would benefit from Groebner Basis preconditioning. These appear to be the first such applications of machine learning to Symbolic Computation. We demonstrate in both cases that the machine learned choice outperforms human developed heuristics.

AB - Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, best known as a procedure to enable Quantifier Elimination over real-closed fields. However, it has a worst case complexity doubly exponential in the size of the input, which is often encountered in practice. It has been observed that for many problems a change in algorithm settings or problem formulation can cause huge differences in runtime costs, changing problem instances from intractable to easy. A number of heuristics have been developed to help with such choices, but the complicated nature of the geometric relationships involved means these are imperfect and can sometimes make poor choices. We investigate the use of machine learning (specifically support vector machines) to make such choices instead. 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 apply it in two case studies: the first to select between heuristics for choosing a CAD variable ordering; the second to identify when a CAD problem instance would benefit from Groebner Basis preconditioning. These appear to be the first such applications of machine learning to Symbolic Computation. We demonstrate in both cases that the machine learned choice outperforms human developed heuristics.

KW - Symbolic computation

KW - Machine Learning

KW - Cylindrical algebraic decomposition

KW - Support Vector Machine

KW - Computer Algebra

KW - Grobner Basis

KW - Parameter Selection

U2 - 10.1007/s11786-019-00394-8

DO - 10.1007/s11786-019-00394-8

M3 - Article

VL - (In-Press)

SP - (In-Press)

JO - Mathematics in Computer Science

JF - Mathematics in Computer Science

SN - 1661-8270

ER -