Fast Multipoint-Evaluation of Bivariate Polynomials

Original · EN

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².⁶⁶⁷) arithmetic operations. In terms of the input size N being quadratic in n, this amounts to an amortized cost of O(N⁰.³³⁴) per point.