A symbolic approach to sparse elimination

Wednesday, June 6, 2007 - 11:15am - 12:15pm
Lind 305
Gabriela Jeronimo (University of Buenos Aires)
Sparse elimination is concerned with 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.

We will discuss a new symbolic procedure for solving zero-dimensional sparse polynomial systems by means of deformation techniques. Roughly speaking, a deformation method to solve a zero-dimensional polynomial equation system works as follows: the input system is regarded as a member of a parametric family of zero-dimensional systems. Then, the solutions to a particular parametric instance which is easy to solve are computed and, finally, these solutions enable one to recover the solutions of the original system.

The algorithm combines the polyhedral deformation introduced by Huber and Sturmfels with symbolic techniques relying on the Newton-Hensel lifting procedure. Its running time can be estimated mainly in terms of the input length and two invariants related to the combinatorial structure underlying the problem.