Fast Multipoint Evaluation of Bivariate Polynomials.

For a preprint see arXiv:cs.DS/0403022.
Pages 544-555 in Proc. 12th Annual European Symposium on Algorithms (ESA 2004), LNCS 3222.

Abstract

We generalize univariate multipoint evaluation of polynomials of degree n at sublinear amortized cost per point. More precisely, it is shown how to evaluate a bivariate polynomial p of maximum degree less than n, specified by its n² coefficients, simultaneously at n² given points using a total of O(n^2.667) arithmetic operations. In terms of the input size N being quadratic in $n$, this amounts to an amortized cost of O(N^0.334) per point.

In the trivariate case, we achieve time O(n^4.334) for evaluation at N=n³ points corresponding to an amortized cost of O(N^0.445) per point.

Michael Nüsken ,