Fast Multipoint-Evaluation of Bivariate Polynomials
| dc.creator | Nüsken, Michael | |
| dc.creator | Ziegler, Martin | |
| dc.date | 2004-03-12 | |
| dc.date | 2004-06-25 | |
| dc.date.accessioned | 2026-07-07T03:21:01Z | |
| dc.date.available | 2026-07-07T03:21:01Z | |
| dc.description | 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. | |
| dc.description | 12 pages, 1 figure. To appear in Proc. 12th ESA 2004 | |
| dc.identifier | https://arxiv.org/abs/cs/0403022 | |
| dc.identifier | http://arxiv.org/abs/cs/0403022 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32040 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F.2.1 | |
| dc.title | Fast Multipoint-Evaluation of Bivariate Polynomials | |
| dc.type | text |