The evaluation of a polynomial at several points is called the problem of multi-point evaluation. We design slightly 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.

Authors: Joris van der Hoeven, Grégoire Lecerf

Keywords: polynomial, multi-point evaluation, algorithm, complexity

View: Html, TeXmacs, Pdf, BibTeX