Evaluation Techniques for Polynomial System Solving

Grégoire Lecerf

I will present a new probabilistic method to compute the decomposition into equidimensional components of the solution set of a system of polynomial equations and inequations. Its complexity is polynomial in an intrinsic degree, of geometrical nature. Our algorithm is implemented in the Kronecker package written in the Magma computer algebra system; We show how its theoretical complexity is well reflected in practice.