Fast Multipoint Evaluation of Bivariate Polynomials

Title: Fast Multipoint Evaluation of Bivariate Polynomials

Abstract: This research focuses on the efficient evaluation of bivariate polynomials at multiple points. The authors propose an algorithm that can evaluate a polynomial of degree n at n2generic points within an average time cost of O(n0.91), which is significantly faster than the sequential evaluation method that requires O(n2) operations. This algorithm is based on the Fast Fourier Transform and fast polynomial arithmetic, which have found applications in various fields such as algorithmic number theory, cryptography, and computational physics.

The main research question addressed in this paper is how to evaluate a bi-variate polynomial of degree n at n2generic points within time O(n2.91), which is an improvement over the sequential evaluation method that requires O(n2) operations. The authors achieve this by embedding and re-substituting the polynomial into uni-variate polynomials of degree O(n2) and then multi-evaluating them using fast polynomial arithmetic.

The algorithm proposed in this paper has significant implications for fields that require the efficient evaluation of polynomials at multiple points, such as computer graphics, computer-aided design, and scientific computing. It opens up new possibilities for faster computations and more efficient algorithms in these areas.

Keywords: Bivariate polynomials, Fast Fourier Transform, Fast polynomial arithmetic, Multi-point evaluation, Generic points, O(n0.91) time complexity

Link to Article: https://arxiv.org/abs/0403022v1 Authors: arXiv ID: 0403022v1