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
Nüsken, Michael;
Ziegler, Martin
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
ISBN
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.
Google Scholar
ISBN Search