Deformation techniques for efficient polynomial equation solving

Suppose we are given a parametric polynomial equation system encoded by an arithmetic circuit, which represents a generically flat and unramified fami ly of zero-dimensional algebraic varieties. Let us also assume that there i s given the complete description of the solution of a particular unramified parameter instance of our system. We show that it is possible to "move" th e given particular solution along the parameter space in order to reconstru ct-by means of an arithmetic circuit-the coordinates of the solutions of th e system for an arbitrary parameter instance. The underlying algorithm is h ighly efficient, i.e., polynomial in the syntactic description of the input and the following geometric invariants: the number of solutions of a typic al parameter instance and the degree of the polynomials occurring in the ou tput. In fact, we prove a slightly more general result, which implies the p revious statement by means of a well-known primitive element algorithm. We produce an efficient algorithmic description of the hypersurfuce obtained p rojecting polynomially the given generically flat family of varieties into a suitable affine space. (C) 2000 Academic Press.