Sparse polynomial arithmetic

Polynomial arithmetic is one of the central topics of computer algebra. It has mainly been studied for polynomials represented by the list of all their coefficients (dense representation). In the case of potentially very high degree polynomials with few nonzero monomials, the so-called sparse representation is more suitable. It consists in storing the exponent-coefficient pairs, but only for the nonzero coefficients.

In this framework, the complexity of the basic operations (multiplication, division, gcd, …) is much less well understood. Until recently, the best algorithms in the general case were naive quadratic algorithms. I will present a series of recent results providing quasi-linear algorithms for exact multiplication and division, as well as improvements on the basic tool used in these algorithms, namely sparse interpolation.

Based on joint works with Pascal Giorgi, Armelle Perret du Cray and Daniel Roche.