Sparse Gröbner Bases: the Unmixed Case


Pierre-Jean Spaenlehauer, Inria Nancy Grand-Est. 12 décembre 2014 10:00 geo 2:00:00
Abstract:

Sparse elimination theory is a framework developed during the last decades to exploit monomial structures in systems of Laurent polynomials by computing in semigroup algebras. We present an analog of Gröbner bases for semigroup algebras, and we propose variants of the algorithms F5 and FGLM to compute them. These objects provide algorithmic tools to compute efficiently the solutions of sparse systems of equations when all the polynomials share the same monomial support (unmixed case). When these monomials correspond 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 this polytope. Our prototype ``proof-of-concept'' implementation shows large speed-ups (more than 100 for some examples) compared to classical Gröbner bases software. Joint work with Jean-Charles Faugère and Jules Svartz.