Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases

Z. Huang; Matthew England; J. H. Davenport; L. C. Paulson

doi:10.1109/SYNASC.2016.020

Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases

Z. Huang, Matthew England, J. H. Davenport, L. C. Paulson

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding › peer-review

18 Citations (Scopus)

88 Downloads (Pure)

Abstract

Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. However, it can be expensive, with worst case complexity doubly exponential in the size of the input. Hence it is important to formulate the problem in the best manner for the CAD algorithm. One possibility is to precondition the input polynomials using Groebner Basis (GB) theory. Previous experiments have shown that while this can often be very beneficial to the CAD algorithm, for some problems it can significantly worsen the CAD performance. In the present paper we investigate whether machine learning, specifically a support vector machine (SVM), may be used to identify those CAD problems which benefit from GB preconditioning. We run experiments with over 1000 problems (many times larger than previous studies) and find that the machine learned choice does better than the human-made heuristic.

Original language	English
Title of host publication	18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
Place of Publication	California
Publisher	IEEE Computer Society
Pages	45-52
ISBN (Print)	978-1-5090-5707-8
DOIs	https://doi.org/10.1109/SYNASC.2016.020
Publication status	Published - 26 Jan 2017
Event	International Symposium on Symbolic and Numeric Algorithms for Scientific Computing - Timisoara, Romania Duration: 24 Sept 2016 → 27 Sept 2016

Conference

Conference	International Symposium on Symbolic and Numeric Algorithms for Scientific Computing
Country/Territory	Romania
City	Timisoara
Period	24/09/16 → 27/09/16

Bibliographical note

© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. ISSN 2470-881X

Keywords

preconditioning
machine learning
support vector machine
computer algebra
cylindrical algebraic decomposition
groebner bases
Computers
Algebra
Machine learning algorithms
Support vector machines
Measurement
Electronic mail
Complexity theory

Access to Document

10.1109/SYNASC.2016.020

Post-printAccepted author manuscript, 518 KB

Dataset supporting "Using Machine Learning to decide when to Precondition Cylindrical Algebraic Decomposition with Groebner Bases"
Huang, Z. (Creator), England, M. (Creator), Davenport, J. H. (Creator) & Paulson, L. C. (Creator), Zenodo, 2017
DOI: 10.5281/zenodo.343885, https://zenodo.org/record/343885
Dataset

Cite this

Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases. / Huang, Z.; England, Matthew; Davenport, J. H. et al.
18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. California: IEEE Computer Society, 2017. p. 45-52.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding › peer-review

Huang, Z, England, M, Davenport, JH & Paulson, LC 2017, Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases. in 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. IEEE Computer Society, California, pp. 45-52, International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, Romania, 24/09/16. https://doi.org/10.1109/SYNASC.2016.020

@inproceedings{759a929a53b94f5bb82a91982c442f7f,

title = "Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases",

abstract = "Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. However, it can be expensive, with worst case complexity doubly exponential in the size of the input. Hence it is important to formulate the problem in the best manner for the CAD algorithm. One possibility is to precondition the input polynomials using Groebner Basis (GB) theory. Previous experiments have shown that while this can often be very beneficial to the CAD algorithm, for some problems it can significantly worsen the CAD performance. In the present paper we investigate whether machine learning, specifically a support vector machine (SVM), may be used to identify those CAD problems which benefit from GB preconditioning. We run experiments with over 1000 problems (many times larger than previous studies) and find that the machine learned choice does better than the human-made heuristic. ",

keywords = "preconditioning, machine learning, support vector machine, computer algebra, cylindrical algebraic decomposition, groebner bases, Computers, Algebra, Machine learning algorithms, Support vector machines, Measurement, Electronic mail, Complexity theory",

author = "Z. Huang and Matthew England and Davenport, {J. H.} and Paulson, {L. C.}",

note = "{\textcopyright} 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. ISSN 2470-881X; International Symposium on Symbolic and Numeric Algorithms for Scientific Computing ; Conference date: 24-09-2016 Through 27-09-2016",

year = "2017",

month = jan,

day = "26",

doi = "10.1109/SYNASC.2016.020",

language = "English",

isbn = " 978-1-5090-5707-8",

pages = "45--52",

booktitle = "18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing",

publisher = "IEEE Computer Society",

address = "United States",

}

TY - GEN

T1 - Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases

AU - Huang, Z.

AU - England, Matthew

AU - Davenport, J. H.

AU - Paulson, L. C.

N1 - © 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. ISSN 2470-881X

PY - 2017/1/26

Y1 - 2017/1/26

N2 - Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. However, it can be expensive, with worst case complexity doubly exponential in the size of the input. Hence it is important to formulate the problem in the best manner for the CAD algorithm. One possibility is to precondition the input polynomials using Groebner Basis (GB) theory. Previous experiments have shown that while this can often be very beneficial to the CAD algorithm, for some problems it can significantly worsen the CAD performance. In the present paper we investigate whether machine learning, specifically a support vector machine (SVM), may be used to identify those CAD problems which benefit from GB preconditioning. We run experiments with over 1000 problems (many times larger than previous studies) and find that the machine learned choice does better than the human-made heuristic.

AB - Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over real-closed fields. However, it can be expensive, with worst case complexity doubly exponential in the size of the input. Hence it is important to formulate the problem in the best manner for the CAD algorithm. One possibility is to precondition the input polynomials using Groebner Basis (GB) theory. Previous experiments have shown that while this can often be very beneficial to the CAD algorithm, for some problems it can significantly worsen the CAD performance. In the present paper we investigate whether machine learning, specifically a support vector machine (SVM), may be used to identify those CAD problems which benefit from GB preconditioning. We run experiments with over 1000 problems (many times larger than previous studies) and find that the machine learned choice does better than the human-made heuristic.

KW - preconditioning

KW - machine learning

KW - support vector machine

KW - computer algebra

KW - cylindrical algebraic decomposition

KW - groebner bases

KW - Computers

KW - Algebra

KW - Machine learning algorithms

KW - Support vector machines

KW - Measurement

KW - Electronic mail

KW - Complexity theory

U2 - 10.1109/SYNASC.2016.020

DO - 10.1109/SYNASC.2016.020

M3 - Conference proceeding

SN - 978-1-5090-5707-8

SP - 45

EP - 52

BT - 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

PB - IEEE Computer Society

CY - California

T2 - International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

Y2 - 24 September 2016 through 27 September 2016

ER -

Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases

Abstract

Conference

Bibliographical note

Keywords

Access to Document

Fingerprint

Datasets

Dataset supporting "Using Machine Learning to decide when to Precondition Cylindrical Algebraic Decomposition with Groebner Bases"

Cite this