COMPUTER SCIENCE COLLOQUIUM

Fast Multipoint Evaluation of Bivariate Polynomials

Martin Ziegler Heinz Nixdorff Institut Universität Paderborn

Tuesday, May 11, 2004, at 14:15 Seminar Room

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.

Host: Klaus Meer

---

SDU HOME | IMADA HOME | Previous Page

---

Last modified: April 23, 2004.

Joan Boyar (joan@imada.sdu.dk)