Details:
Title  A Gröbner Free Alternative for Polynomial
System Solving  Author(s)  Marc Giusti, Gregoire Lecerf, Bruno Salvy  Type  Article in Journal  Abstract  Given a system of polynomial equations and inequations with coefficients in the field of rational numbers, we show how to compute a geometric resolution of the set of common roots of the system over the field of complex numbers. A geometric resolution consists of a primitive element of the algebraic extension defined by the set of roots, its minimal polynomial and the parametrizations of the coordinates. Such a representation of the solutions has a long history which goes back to Leopold Kronecker and has been revisited many times in computer algebra. We introduce a new generation of probabilistic algorithms where all the computations use only univariate or bivariate polynomials. We give a new codification of the set of solutions of a positive dimensional algebraic variety relying on a new global version of Newton's iterator. Roughly speaking the complexity of our algorithm is polynomial in some kind of degree of the system, in its height, and linear in the complexity of evaluation of the system.
We present our implementation in the Magma system which is called Kronecker in homage to this method for solving systems of polynomial equations. We show that the theoretical complexity of our algorithm is well reflected in practice and we exhibit some cases for which our program is more efficient than the other available softwares.  Keywords  polynomial system solving, elimination, geometric resolution  Length  58  Copyright  Academic Press 
File 
 URL 
doi:10.1006/jcom.2000.0571 
Language  English  Journal  Journal of Complexity  Volume  17  Number  1  Pages  154  211  Year  2001  Month  March  Edition  0  Translation 
No  Refereed 
No 
