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

Zongyan Huang, Matthew England, James Davenport, Lawrence Paulson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)
76 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 languageEnglish
Title of host publicationProceedings of the 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016
EditorsJames Davenport
PublisherIEEE
Pages45-52
ISBN (Print)9781509057085
DOIs
Publication statusPublished - 26 Jan 2017

Fingerprint

Learning systems
Decomposition
Computational geometry
Support vector machines
Experiments
Polynomials

Cite this

Huang, Z., England, M., Davenport, J., & Paulson, L. (2017). Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases. In J. Davenport (Ed.), Proceedings of the 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016 (pp. 45-52). [7829592] IEEE. https://doi.org/10.1109/SYNASC.2016.020

Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases. / Huang, Zongyan; England, Matthew; Davenport, James; Paulson, Lawrence.

Proceedings of the 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016. ed. / James Davenport. IEEE, 2017. p. 45-52 7829592.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Huang, Z, England, M, Davenport, J & Paulson, L 2017, Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases. in J Davenport (ed.), Proceedings of the 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016., 7829592, IEEE, pp. 45-52. https://doi.org/10.1109/SYNASC.2016.020
Huang Z, England M, Davenport J, Paulson L. Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases. In Davenport J, editor, Proceedings of the 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016. IEEE. 2017. p. 45-52. 7829592 https://doi.org/10.1109/SYNASC.2016.020
Huang, Zongyan ; England, Matthew ; Davenport, James ; Paulson, Lawrence. / Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases. Proceedings of the 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016. editor / James Davenport. IEEE, 2017. pp. 45-52
@inproceedings{0665724a623d40c08934afb7c92311c7,
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.",
author = "Zongyan Huang and Matthew England and James Davenport and Lawrence Paulson",
year = "2017",
month = "1",
day = "26",
doi = "10.1109/SYNASC.2016.020",
language = "English",
isbn = "9781509057085",
pages = "45--52",
editor = "James Davenport",
booktitle = "Proceedings of the 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016",
publisher = "IEEE",
address = "USA United States",

}

TY - GEN

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

AU - Huang, Zongyan

AU - England, Matthew

AU - Davenport, James

AU - Paulson, Lawrence

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.

UR - http://dx.doi.org/10.1109/SYNASC.2016.020

U2 - 10.1109/SYNASC.2016.020

DO - 10.1109/SYNASC.2016.020

M3 - Conference contribution

SN - 9781509057085

SP - 45

EP - 52

BT - Proceedings of the 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016

A2 - Davenport, James

PB - IEEE

ER -