Abstract
Cylindrical Algebraic Decomposition (CAD) is a key tool in computational algebraic geometry, particularly for quantifier elimination over realclosed 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 humanmade 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  4552 
ISBN (Print)  9781509057078 
DOIs  
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 2470881XKeywords
 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
Fingerprint
Dive into the research topics of 'Using Machine Learning to Decide When to Precondition Cylindrical Algebraic Decomposition With Groebner Bases'. Together they form a unique fingerprint.Datasets

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