Faster multi-point evaluation over any field

Joris van der Hoeven; Grégoire Lecerf

doi:10.1007/s00200-025-00704-7

Faster multi-point evaluation over any field

Research output: Contribution to journal › Article › peer-review

Abstract

The evaluation of a polynomial at several points is called the problem of multi-point evaluation. We design new faster deterministic algorithms to solve this problem for an algebraic computational model. For this purpose, we analyze the precomputation costs of recent amortized evaluation algorithms, and then study the complexity of the problem as a function of the number of evaluation points.

Original language	English
Journal	Applicable Algebra in Engineering, Communication and Computing
DOIs	https://doi.org/10.1007/s00200-025-00704-7
Publication status	Accepted/In press - 1 Jan 2025

Keywords

Algorithm
Complexity
Multi-point evaluation
Polynomial

Access to Document

10.1007/s00200-025-00704-7

Cite this

@article{a56c83eddc944bc0a9c6ea12b98fe619,

title = "Faster multi-point evaluation over any field",

abstract = "The evaluation of a polynomial at several points is called the problem of multi-point evaluation. We design new faster deterministic algorithms to solve this problem for an algebraic computational model. For this purpose, we analyze the precomputation costs of recent amortized evaluation algorithms, and then study the complexity of the problem as a function of the number of evaluation points.",

keywords = "Algorithm, Complexity, Multi-point evaluation, Polynomial",

author = "\{van der Hoeven\}, Joris and Gr{\'e}goire Lecerf",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2025.",

year = "2025",

month = jan,

day = "1",

doi = "10.1007/s00200-025-00704-7",

language = "English",

journal = "Applicable Algebra in Engineering, Communication and Computing",

issn = "0938-1279",

}

TY - JOUR

T1 - Faster multi-point evaluation over any field

AU - van der Hoeven, Joris

AU - Lecerf, Grégoire

N1 - Publisher Copyright: © The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2025.

PY - 2025/1/1

Y1 - 2025/1/1

N2 - The evaluation of a polynomial at several points is called the problem of multi-point evaluation. We design new faster deterministic algorithms to solve this problem for an algebraic computational model. For this purpose, we analyze the precomputation costs of recent amortized evaluation algorithms, and then study the complexity of the problem as a function of the number of evaluation points.

AB - The evaluation of a polynomial at several points is called the problem of multi-point evaluation. We design new faster deterministic algorithms to solve this problem for an algebraic computational model. For this purpose, we analyze the precomputation costs of recent amortized evaluation algorithms, and then study the complexity of the problem as a function of the number of evaluation points.

KW - Algorithm

KW - Complexity

KW - Multi-point evaluation

KW - Polynomial

UR - https://www.scopus.com/pages/publications/105013470140

U2 - 10.1007/s00200-025-00704-7

DO - 10.1007/s00200-025-00704-7

M3 - Article

AN - SCOPUS:105013470140

SN - 0938-1279

JO - Applicable Algebra in Engineering, Communication and Computing

JF - Applicable Algebra in Engineering, Communication and Computing

ER -

Faster multi-point evaluation over any field

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this