Projects per year
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.
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  Proceedings of the 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2016 
Editors  James Davenport 
Publisher  IEEE 
Pages  4552 
ISBN (Print)  9781509057085 
DOIs  
Publication status  Published  26 Jan 2017 
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.
Projects
 1 Finished

Real Geometry and Connectedness via Triangular Description
Davenport, J., Bradford, R., England, M. & Wilson, D.
Engineering and Physical Sciences Research Council
1/10/11 → 31/12/15
Project: Research council