Global projection operators for the Cylindrical Algebraic Decomposition algorithm
Date: July 19th (Friday)
Time: 14:40-15:00
Abstract
The projection phase in the CAD algorithm proceeds by eliminating one
variable on a given set of polynomials X via the computation of the
principal subresultant coefficients of a well precised set of polynomials
pairs on X (including their derivatives and their reductums). Since the
size, at least in number, of this new set of polynomials is usually very
big, any improvement in the projection phase would convey to dramatically
speed up the efficiency of the CAD algorithm.
The purpose of this talk is to present two approaches allowing, in some
cases, to simplify the projection phase in the CAD algorithm:
-. The first one tries to avoid the consideration of all the different pairs
of polynomials and their reductums by parametrizing the rank of a well
precised matrix with polynomial entries.
-. The second one tries to perform an improved projection phase through the
elimination of blocks of variables instead of the usual one by one
variable elimination.
The theoretical tools to be used include Barnett's Theorem characterizing
the degree of the gcd of a finite set of polynomials through the rank of a
well-precised matrix and the parametrization of Hermite's Method for
counting the number of real solutions of a polynomial system of equations.
