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

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
journal	Applicable Algebra in Engineering, Communication and Computing
Les DOIs	https://doi.org/10.1007/s00200-025-00704-7
état	Accepté/En presse - 1 janv. 2025

Accès au document

10.1007/s00200-025-00704-7

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@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

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation