Sep 18 – 29, 2023
Institut Henri Poincaré
Europe/Paris timezone

Modulus tricks for integer sparse polynomials by Daniel Roche

Sep 29, 2023, 11:00 AM
Amphithéâtre Hermite / Darboux (Institut Henri Poincaré)

Amphithéâtre Hermite / Darboux

Institut Henri Poincaré

11 rue Pierre et Marie Curie 75005 Paris


Abstract. Sparse polynomials with integer coefficients are a basic building block in computer algebra systems, as well as an important fundamental object for algorithmic study. Since at least the 1980s, efficient algorithms have been constructed based on the flexibility afforded by changing the integer modulus repeatedly during the computation. This talk will attempt to briefly survey some of the modulus-choosing techniques employed in recent results to achieve faster algorithms. We will also briefly examine when these techniques (fail to) extend to the case of floating point computations and field extensions.

Presentation materials

There are no materials yet.