A grobner free alternative for polynomial system solving

Given a system of polynomial equations and inequations with coefficients in the field of rational numbers, we show how to compute a geometric resoluti on of the set of common roots of the system over the field of complex numbe rs. A geometric resolution consists of a primitive element of the algebraic extension defined by the let of roots. its minimal polynomial, and the par ameterizations of the coordinates. Such a representation of the solutions h as a long history which goes back to Leopold Kronecker and has been revisit ed many times in computer algebra. We introduce a new generation of probabi listic algorithms where all the computations use only univariate or bivaria te polynomials. Wa give a new codification of the set of solutions of a pos itive dimensional algebraic variety relying on a new global version of Newt on's iterator. Roughly speaking the complexity of our algorithm is polynomi al in some kind of degree of the system, in its height, and linear in the c omplexity of evaluation of the system. We present our implementation in the Magma system which is called Kronecker in homage to his method for solving systems of polynomial equations. We show that the theoretical complexity o f our algorithm is well reflected in practice and we exhibit some cases for which our program is more efficient than the other available software. (C) 2001 Academic Press.