In this paper, we present a new algorithm for reducing a multivariate polynomial with respect to an autoreduced tuple of other polynomials. In a suitable sparse complexity model, it is shown that the execution time is essentially the same (up to a logarithmic factor) as the time needed to verify that the result is correct. This is a first step towards making advantage of fast sparse polynomial arithmetic for the computation of Gröbner bases.

Authors: Joris van der Hoeven

Keywords: sparse reduction, complexity, division, Gröbner basis, algorithm

A.M.S. subject classification: 68W30, 13P10, 12Y05, 68W40

View: Html, TeXmacs, Pdf, BibTeX

ACA version: Html, TeXmacs, Pdf, BibTeX