Parallel Sparse Polynomial Interpolation over Finite Fields

Mahdi Javadi, School of Computing Science, SFU.

Wednesday July 7th, in K9509 at 3:30pm.


We present a probabilistic algorithm to interpolate a sparse multivariate
polynomial over a finite field, represented with a black box.  Our algorithm
modifies the algorithm of Ben-Or and Tiwari from 1988 for interpolating
polynomials over rings with characteristic zero to characteristic $p$ by
doing additional probes.

To  interpolate a polynomial in n variables with t non-zero terms, Zippel's
algorithm interpolates one variable at a time using O(ndt) probes to the
black box where d bounds the degree of the polynomial.  Our new algorithm
does O(nt) probes.  It interpolates each variable independently using O(t)
probes which allows us to parallelize the main loop giving an advantage
over Zippel's algorithm.

We have implemented both Zippel's algorithm and the new algorithm in C
and we have done a parallel implementation of our algorithm using Cilk.
In the talk we provide benchmarks comparing the number of probes our
algorithm does with both Zippel's algorithm and Kaltofen and Lee's hybrid
of the Zippel and Ben-Or/Tiwari algorithms.  The benchmarks also 
demonstrate how effective our parallel implementation is.