A symbolic procedure for solving sparse polynomial equation systems

GABRIELA JERONIMO

Medellín, Colombia

Conferencia; XVII Coloquio Latinoamericano de Álgebra; 2007

The Bernstein-Kushnirenko-Khovanskii theorem asserts that the number of isolated solutions in (C^*)^n  of a polynomial system of n equations in n unknowns is bounded above by the mixed volume of the family of Newton polytopes of the system. For sparse systems, this number canbe signifficantly lower than the upper bound given by the the classical Bézout theorem in terms of the degrees of the polynomials and so, the complexity of their resolution is expected to be lower than that for the general case. We will present a symbolic procedure for solving sparse zero-dimensional polynomial equation systems whose running time can be expressed mainly in terms of invariants related to the combinatorial structure underlying the problem. Assuming the combinatorics is known, the algorithm combines the polyhedral deformation introduced by Huber and Sturmfels with symbolic techniques relying on the Newton-Hensel lifting procedure in order to compute a geometric solution of the zero set of the input system within a complexity which is linear in the input size and quadratic in certain associated mixed volumes. (Joint work with Guillermo Matera, Pablo Solernó and Ariel Waissbein.)