[ Homepage | Publications | Talks | TeXmacs |
Mathemagix ] |

Sparse polynomial interpolation consists in recovering of a sparse representation of a polynomial given by a blackbox program which computes values of at as many points as necessary. In practice is typically represented by DAGs (Directed Acyclic Graphs) or SPLs (Straight Line Programs). For polynomials with at most terms over a field , this task typically involves evaluations of , operations on integers for discovering the exponents of the nonzero terms of , and an additional number of operations in that can be bounded by for recovering the coefficients.

However, the latter complexity analysis does not take into account the sizes of coefficients in and the expression swell that might occur when evaluating at points with high height. For practical implementations, it is important to perform most of the computations over a prime finite field , where fits into a single machine register. On modern architectures, this typically means that . There mainly are two approaches which can be used over finite fields: the “prime number” approach and the “Kronecker substitution” approach. We present new techniques which can be used to further enhance and combine these classical approaches.

We report on our implementations in the

**Occasion:** Software presentation, ISSAC 2014, Kobe, July
23, 2014

**Award:** Distinguished software presentation at ISSAC
2014

**Coauthor:** Grégoire

**Documents:** slideshow, TeXmacs
source