Towards faster practical sparse polynomial interpolation (Part I)


Consider a program that computes actually computes a sparse polynomial in . The problem of sparse polynomial interpolation consists of determining this polynomial in its usual representation from the evaluations of at sufficiently many well chosen points.

In our talk, we will survey various approaches to solve this problem. We mainly focus on possibly heuristic algorithms that are most efficient in practice and on the particular case when has coefficients in a finite field.

Occasion: computer algebra seminar, SFU, Burnaby, Canada, December 2, 2019

Documents: slideshow, TeXmacs source