![]() |
Towards faster practical sparse polynomial interpolation.Joris van der Hoven, Laboratoire d'informatique de l'École polytechnique, Paris.
Abstract: Consider a program f(x1,...,xn) that actually computes a sparse polynomial in x1,...,xn. The problem of sparse polynomial interpolation consists of determining this polynomial in its usual representation from the evaluations of f 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. |