Solving sparse polynomial systems by computing Gröbner bases faster

Gröbner bases are one the most powerful tools in algorithmic nonlinear algebra and a standard tool to solve polynomial systems. Their computation is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. For example, several problems in computer-aided design, robotics, vision, biology, kinematics, cryptography, and optimization involve sparse systems where the input polynomials have a few non-zero terms.

In this talk, we discuss how to solve polynomial systems faster by exploiting their sparsity. We do so by introducing tools coming from toric geometry to the Gröbner-basis framework. Our strategy is to perform our computations over multigraded semigroup algebras associated to the Newton polytopes of the input systems. We present the first algorithm to compute Gröbner bases for sparse systems that, under regularity assumptions, performs no redundant computations. Additionally, we discuss the complexity of our approach, its dependence on the combinatorics of the input polytopes and how, for particular families of sparse systems, we can use the multigraded Castelnuovo-Mumford regularity to improve our complexity bounds.