Fast Multipoint Evaluation of Bivariate Polynomials

M. Nüsken, M. Ziegler, in: Proc. 12th Annual Symposium on Algorithms (ESA’04), Springer, Berlin, Heidelberg, 2004, pp. 544–555.

Download
No fulltext has been uploaded.
Conference Paper | Published | English
Author
;
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^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.
Publishing Year
Proceedings Title
Proc. 12th Annual Symposium on Algorithms (ESA'04)
Volume
3221
Page
544-555
LibreCat-ID

Cite this

Nüsken M, Ziegler M. Fast Multipoint Evaluation of Bivariate Polynomials. In: Proc. 12th Annual Symposium on Algorithms (ESA’04). Vol 3221. Berlin, Heidelberg: Springer; 2004:544-555. doi:10.1007/978-3-540-30140-0_49
Nüsken, M., & Ziegler, M. (2004). Fast Multipoint Evaluation of Bivariate Polynomials. In Proc. 12th Annual Symposium on Algorithms (ESA’04) (Vol. 3221, pp. 544–555). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-540-30140-0_49
@inproceedings{Nüsken_Ziegler_2004, place={Berlin, Heidelberg}, title={Fast Multipoint Evaluation of Bivariate Polynomials}, volume={3221}, DOI={10.1007/978-3-540-30140-0_49}, booktitle={Proc. 12th Annual Symposium on Algorithms (ESA’04)}, publisher={Springer}, author={Nüsken, Michael and Ziegler, Martin}, year={2004}, pages={544–555} }
Nüsken, Michael, and Martin Ziegler. “Fast Multipoint Evaluation of Bivariate Polynomials.” In Proc. 12th Annual Symposium on Algorithms (ESA’04), 3221:544–55. Berlin, Heidelberg: Springer, 2004. https://doi.org/10.1007/978-3-540-30140-0_49.
M. Nüsken and M. Ziegler, “Fast Multipoint Evaluation of Bivariate Polynomials,” in Proc. 12th Annual Symposium on Algorithms (ESA’04), 2004, vol. 3221, pp. 544–555.
Nüsken, Michael, and Martin Ziegler. “Fast Multipoint Evaluation of Bivariate Polynomials.” Proc. 12th Annual Symposium on Algorithms (ESA’04), vol. 3221, Springer, 2004, pp. 544–55, doi:10.1007/978-3-540-30140-0_49.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search