Sparse elimination: a symbolic approach using deformation techniques

GABRIELA JERONIMO

Luminy, Francia

Conferencia; Elimination theory and applications (in honor of Jean Pierre Jouanolou); 2006

Sparse elimination is concerned with solving systems of polynomial equations in which each equation is given by a polynomial having non-zero coefficients only for those monomials lying in a prescribed set. The Bernstein-Kushnirenko-Khovanskii theorem asserts that the number of isolated solutions in the n-dimensional complex torus (C^∗)^n of a polynomial system of n equations in n unknowns is bounded by the mixed volume of the family of Newton polytopes of the system. For a sparse system, this number can be significantly lower than the upper bound given by the Bezout theorem in terms of the degrees of the polynomials and so, the complexity for their computation should also be lower than that for the general case. We will discuss a new symbolic procedure for sparse elimination whose complexity can be expressed mainly in terms of two invariants related to the combinatorial structure underlying the problem. The algorithm combines the polyhedral deformation introduced by Huber and Sturmfels for solving sparse polynomial systems, with the symbolic techniques relying on the Newton-Hensel lifting procedure applied by Giusti, Heintz and their collaborators in the general polynomial system solving framework. (Joint work with Guillermo Matera, Pablo Solerno and Ariel Waissbein.)