TY - CONF
AB - 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^2 coefficients, simultaneously at n^2 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.
AU - NÃ¼sken, Michael
AU - Ziegler, Martin
ID - 18263
SN - 0302-9743
T2 - Proc. 12th Annual Symposium on Algorithms (ESA'04)
TI - Fast Multipoint Evaluation of Bivariate Polynomials
VL - 3221
ER -