Speeding up Cylindrical Algebraic Decomposition by Gröbner Bases

Abstract

Gröbner Bases and Cylindrical Algebraic Decomposition are generally thought of as two, rather different, methods of looking at systems of equations and, in the case of Cylindrical Algebraic Decomposition, inequalities. However, even for a mixed system of equalities and inequalities, it is possible to apply Gröbner bases to the (conjoined) equalities before invoking CAD. We see that this is, quite often but not always, a beneficial preconditioning of the CAD problem. It is also possible to precondition the (conjoined) inequalities with respect to the equalities, and this can also be useful in many cases.

To appear in Proc. CICM 2012, LNCS 7362

Cited by in corpus (8)

• Truth Table Invariant Cylindrical Algebraic Decomposition
• Cylindrical Algebraic Decomposition with Equational Constraints
• Using Machine Learning to Improve Cylindrical Algebraic Decomposition
• The complexity of cylindrical algebraic decomposition with respect to polynomial degree
• Conormal Spaces and Whitney Stratifications
• Machine Learning for Mathematical Software
• An implementation of CAD in Maple utilising McCallum projection
• An Incremental Algorithm for Computing Cylindrical Algebraic Decompositions