Characterization of the Affine Solutions of Sparse Polynomial Systems

MARÍA ISABEL HERRERO; GABRIELA JERONIMO; JUAN SABIA

Berkeley, California

Workshop; Workshop on Solving Polynomial Equations; 2014

Simons Institute for the theory of computing, Universidad de Berkeley

The effective resolution of systems of polynomial equations is a mathematical problem of fundamental importance, both from a practical and a theoretical standpoint. Given a set of polynomial equations in n variables, and, in view of the applications, the aim is to describe algorithmically the set of its solutions in C^n taking into account the support set of the polynomials involved (that is, the set of monomials that appear with non-zero coefficients). Unlike the case of dense polynomials, the affine varieties defined by sparse systems (systems with pre-fixed support sets) of n polynomials, even in the generic case, can have components of positive dimension in coordinate linear spaces. In this talk I will present conditions on the set of supports of (not necessarily square) systems that allow us to determine the existence of these components in the generic case, and a symbolic algorithm for their computation. If there is some time left, I will overview the non generic case for systems of n polynomials presenting an upper bound for the degree of the variety the system defines and an algorithm to find witness points in every irreducible component within a complexity which is polynomial in our bound for the degree. Joint work with Gabriela Jeronimo and Juan Sabia. http://simons.berkeley.edu/talks/maria-isabel-herrero-2014-10-14