Towards faster practical sparse polynomial interpolation (Part II)


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 f has coefficients in a finite field.

Occasion: computer algebra seminar, SFU, Burnaby, Canada, January 14, 2020

Documents: slideshow, TeXmacs source