Deformation techniques for sparse polynomial systems

GABRIELA JERONIMO; GUILLERMO MATERA; PABLO SOLERNÓ; ARIEL WAISSBEIN

Hong Kong

Conferencia; Foundations of Computational Mathematics Conference 2008 (FOCM'08); 2008

Society for the Foundations of Computational Mathematics

In this talk we present a probabilistic symbolic algorithm for solving zero-dimensional sparse systems, namely, systems defined by polynomials with nonzero coefficients only at a prescribed set of monomials. Our algorithm combines a symbolic homotopy procedure, based on a flat deformation of a certain morphism of affine varieties, with the polyhedral deformation of Huber and Sturmfels. The complexity of our algorithm is cubic in the size of the combinatorial structure of the input system. This size is mainly represented by the cardinality and mixed volume of Newton polytopes of the input polynomials and an arithmetic analogue of the mixed volume associated to the deformations under consideration.