Evaluating sparse polynomials at many points.

Michael Monagan, CECM

Wednesday May 11th at 1:30pm in K9509.


Let A(x1,x2,...,xn) be a sparse polynomial over a prime field with S non-zero terms.
Given a point (a1,a2,...,an), how fast can we compute the T values A(a1k,a2k,...,ank)
for k=1,2,...,T?  

This evaluation problem arises in multivariate polynomial GCD computation.
We present three methods.