Details:
Title  Deformation Techniques for Efficient Polynomial Equation Solving  Author(s)  Joos Heintz, Teresa Krick, Susana Puddu, Juan Sabia, Ariel Waissbein  Type  Article in Journal  Abstract  Suppose we are given a parametric polynomial equation system encoded by an arithmetic circuit, which represents a generically flat and unramified family of zerodimensional algebraic varieties. Let us also assume that there is given the complete description of the solution of a particular unramified parameter instance of our system. We show that it is possible to "move" the given particular solution along the parameter space in order to reconstruct—by means of an arithmetic circuit—the coordinates of the solutions of the system for an arbitrary parameter instance. The underlying algorithm is highly efficient, i.e., polynomial in the syntactic description of the input and the following geometric invariants: the number of solutions of a typical parameter instance and the degree of the polynomials occurring in the output. In fact, we prove a slightly more general result, which implies the previous statement by means of a wellknown primitive element algorithm. We produce an efficient algorithmic description of the hypersurface obtained projecting polynomially the given generically flat family of varieties into a suitable affine space.  Keywords  polynomial equation system, arithmetic circuit, shape (or primitive element) lemma, Newton 3, Hensel iteration  Length  40  Copyright  Academic Press 
File 
 URL 
dx.doi.org/10.1006/jcom.1999.0529 
Language  English  Journal  Journal of Complexity  Volume  16  Number  1  Pages  70109  Year  2000  Month  March  Translation 
No  Refereed 
No 
