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

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

doi:10.1007/978-3-319-08434-3_8

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

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

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

45 Citations (SciVal)

171 Downloads (Pure)

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.

Original language	English
Title of host publication	Intelligent Computer Mathematics
Editors	Stephen M. Watt, James H. Davenport, Alan P. Sexton, Petr Sojka, Joesf Urban
Publisher	Springer
Pages	92-107
Number of pages	16
Volume	8543
ISBN (Electronic)	9783319084343
ISBN (Print)	9783319084336
DOIs	https://doi.org/10.1007/978-3-319-08434-3_8
Publication status	Published - 2014

Publication series

Name	Lecture Notes in Artificial Intelligence
Publisher	Springer

Keywords

machine learning
support vector machine
symbolic computation
cylindrical algebraic decomposition
problem formulation

Access to Document

10.1007/978-3-319-08434-3_8

Author's accepted version
The final publication will be available from http://link.springer.com/
Accepted author manuscript, 198 KB

Cite this

Huang, Z., England, M., Wilson, D., Davenport, J. H., Paulson, L., & Bridge, J. (2014). Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition. In S. M. Watt, J. H. Davenport, A. P. Sexton, P. Sojka, & J. Urban (Eds.), Intelligent Computer Mathematics (Vol. 8543, pp. 92-107). (Lecture Notes in Artificial Intelligence). Springer. https://doi.org/10.1007/978-3-319-08434-3_8

Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition. / Huang, Zongyan; England, Matthew; Wilson, David et al.
Intelligent Computer Mathematics. ed. / Stephen M. Watt; James H. Davenport; Alan P. Sexton; Petr Sojka; Joesf Urban. Vol. 8543 Springer, 2014. p. 92-107 (Lecture Notes in Artificial Intelligence).

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

Huang, Z, England, M, Wilson, D, Davenport, JH, Paulson, L & Bridge, J 2014, Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition. in SM Watt, JH Davenport, AP Sexton, P Sojka & J Urban (eds), Intelligent Computer Mathematics. vol. 8543, Lecture Notes in Artificial Intelligence, Springer, pp. 92-107. https://doi.org/10.1007/978-3-319-08434-3_8

Huang Z, England M, Wilson D, Davenport JH, Paulson L, Bridge J. Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition. In Watt SM, Davenport JH, Sexton AP, Sojka P, Urban J, editors, Intelligent Computer Mathematics. Vol. 8543. Springer. 2014. p. 92-107. (Lecture Notes in Artificial Intelligence). doi: 10.1007/978-3-319-08434-3_8

Huang, Zongyan ; England, Matthew ; Wilson, David et al. / Applying machine learning to the problem of choosing a heuristic to select the variable ordering for cylindrical algebraic decomposition. Intelligent Computer Mathematics. editor / Stephen M. Watt ; James H. Davenport ; Alan P. Sexton ; Petr Sojka ; Joesf Urban. Vol. 8543 Springer, 2014. pp. 92-107 (Lecture Notes in Artificial Intelligence).

@inbook{b8f51380ddfa42f095587c11a1e61f6a,

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

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

keywords = "machine learning, support vector machine, symbolic computation, cylindrical algebraic decomposition, problem formulation",

author = "Zongyan Huang and Matthew England and David Wilson and Davenport, {James H.} and Lawrence Paulson and James Bridge",

year = "2014",

doi = "10.1007/978-3-319-08434-3_8",

language = "English",

isbn = "9783319084336",

volume = "8543",

series = "Lecture Notes in Artificial Intelligence",

publisher = "Springer",

pages = "92--107",

editor = "Watt, {Stephen M.} and Davenport, {James H.} and Sexton, {Alan P. } and Petr Sojka and Joesf Urban",

booktitle = "Intelligent Computer Mathematics",

}

TY - CHAP

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

AU - Huang, Zongyan

AU - England, Matthew

AU - Wilson, David

AU - Davenport, James H.

AU - Paulson, Lawrence

AU - Bridge, James

PY - 2014

Y1 - 2014

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

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

KW - machine learning

KW - support vector machine

KW - symbolic computation

KW - cylindrical algebraic decomposition

KW - problem formulation

UR - http://cicm-conference.org/2014/cicm.php?event=&menu=general

UR - http://dx.doi.org/10.1007/978-3-319-08434-3_8

U2 - 10.1007/978-3-319-08434-3_8

DO - 10.1007/978-3-319-08434-3_8

M3 - Chapter or section

SN - 9783319084336

VL - 8543

T3 - Lecture Notes in Artificial Intelligence

SP - 92

EP - 107

BT - Intelligent Computer Mathematics

A2 - Watt, Stephen M.

A2 - Davenport, James H.

A2 - Sexton, Alan P.

A2 - Sojka, Petr

A2 - Urban, Joesf

PB - Springer

ER -

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

Abstract

Publication series

Keywords

Access to Document

Other files and links

Fingerprint

Real Geometry and Connectedness via Triangular Description

Cite this

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

Abstract

Publication series

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Real Geometry and Connectedness via Triangular Description

Cite this