Fast Multipoint-Evaluation of Bivariate Polynomials

2004/03/12 by Michael Nüsken, Martin Ziegler, Nüsken, Michael +1 · 1 citation
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #Polynomial and algebraic computation #cs.DS

paper · pdf · doi:10.48550/arxiv.cs/0403022

12 pages, 1 figure. To appear in Proc. 12th ESA 2004

openalex publication_date 2004/03/12 · arxiv created 2004/06/25 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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² coefficients, simultaneously at n² 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.

Cited by

• A Simple Algorithm for Trimmed Multipoint Evaluation

Related

• A Simple Algorithm for Trimmed Multipoint Evaluation
• Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications
• Fast Multivariate Multipoint Evaluation Over All Finite Fields
• Fast Approximate Polynomial Multipoint Evaluation and Applications
• Fast Evaluation of Real and Complex Polynomials