Computing isolated roots of sparse polynomial systems in affine space

HERRERO, MARÍA ISABEL; JERONIMO, GABRIELA; SABIA, JUAN

THEORETICAL COMPUTER SCIENCE

ELSEVIER SCIENCE BV

Año: 2010 vol. 411 p. 3894 - 3904

0304-3975

We present a symbolic probabilistic algorithm to compute the isolated roots in C^n of  sparse polynomial equation systems. As some already known numerical algorithms solving this task, our procedure is based on polyhedral deformations and homotopies, but it amounts to solving a smaller number of square systems of equations and in fewer variables. The output of the algorithm is a emph{geometric resolution} of a finite set of points including the isolated roots of the system. The complexity is polynomial in the size of the combinatorial structure of the system supports up to a pre-processing yielding the mixed cells in a subdivision of the family of these supports.