27/06/2014

Intervenant(s) : Jules Svartz (PolSys team, CNRS/INRIA/UPMC)

Toric (or sparse) elimination theory is a framework developped during the last decades to exploit monomial structures in systems of Laurent polynomials. Roughly speaking, this amounts to computing in a semigroup algebra, i.e. an algebra generated by a subset of Laurent monomials.

In this talk, I will explain a new approach mixing this framework with Gröbner bases. In order to solve symbolically sparse systems, we introduce sparse Gröbner bases, an analog of classical Gröbner bases for semigroup algebras, and we propose sparse variants of the F5 and FGLM algorithms to compute them. Our prototype "proof-of-concept" implementation shows large speed-ups (more than 100 for some examples) compared to optimized (classical) Gröbner bases software.

Moreover, in the case where the generating subset of monomials corresponds to the points with integer coordinates in a normal lattice polytope and under regularity assumptions, we prove complexity bounds which depend on the combinatorial properties of the polytope. These bounds yield new estimates on the complexity of solving zero-dimensional systems where all polynomials share the same Newton polytope (the so-called unmixed case). For instance, we generalize the bound $min(n_1,n_2)+1$ on the maximal degree in a Gröbner basis of a zero-dimensional bilinear system with blocks of variables of sizes $(n_1,n_2)$ to the multilinear case: $sum n_i - max(n_i)+1$. We also propose a variant of Fröberg's conjecture which allows us to estimate the complexity of solving overdetermined sparse systems.

Joint Work with Jean-Charles Faugère and Pierre-Jean Spaenlehauer.

Elias.Tsigaridas (at) nulllip6.fr