Fast Multipoint-Evaluation of Bivariate Polynomials
<|reference_start|>Fast Multipoint-Evaluation of Bivariate Polynomials: 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.<|reference_end|>
@article{nüsken2004fast,
    title={Fast Multipoint-Evaluation of Bivariate Polynomials},
    author={Michael N"usken, Martin Ziegler},
    journal={arXiv preprint arXiv:cs/0403022},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0403022},
    primaryClass={cs.DS}
}