Algorithms for solving sparse polynomial systems

MARÍA ISABEL HERRERO; GABRIELA JERONIMO; JUAN SABIA

Daejeon

Conferencia; SIAM Conference on Applied Algebraic Geometry (AG15); 2015

SOciety for Industrial and Applied Mathematics (SIAM)

Polynomial system solving is a fundamental problem both from apractical and a theoretical point of view. Considering itsapplications, it is of special interest the study of sparse polynomialsystems, that is, systems given by polynomials that involve monomialsin prefixed sets. Bernstein's theorem, which is considered the basisof the study of sparse polynomial systems, led to the development ofsparse elimination theory.A wide variety of effective numerical and symbolic algorithms forsolving sparse systems have been developed. In joint works withGabriela Jeronimo and Juan Sabia, we presented new probabilisticalgorithms that, combining symbolic methods with techniques fromnumerical algebraic geometry, have complexity bounds depending ongeometric-combinatorial invariants associated with the support set ofthe input polynomials. I will present an overview of these results andexplain how we use numerical tools such as witness sets in thesymbolic context.