Fast Polynomial Evaluation (présentation + demo)

The FPE algorithm is backed by a mathematical result on the parcimonious representation of

polynomials. Our article [1] contains a detailed analysis of the complexity and a full error analysis,

which guarantees that the algorithm performs as well as H¨orner’s scheme, only faster. Our algorithm is

implemented in a companion library, written in standard C and released as an open-source project [2].

Our claims regarding complexity and accuracy are confirmed in practice by a set of comprehensive

benchmarks.

This work is a spin-off in a general research program regarding high-degree polynomials and new

numerical methods for complex dynamics. During JCAD 2021 [3], we had presented the successful

splitting of a polynomial of degree 1012, that is of interest for the study of the Mandelbrot set.



In a 20 minutes talk, we would like to present the FPE algorithm. The underlying principles (lazy

addition and a geometric selection principle based on convexity) are simple enough and can be of interest

to a wide audience. No technical mathematical background is required. We will also explain how we

used the infrastructure of the HPC Center Romeo (Reims) to perform systematic benchmarks

References

[1] R. Anton, N. Mihalache, F. Vigneron. Fast evaluation of real and complex polynomials. Preprint

2022, HAL-03820369 / arXiv:2211.06320.

[2] N. Mihalache, F. Vigneron. FPE library : https://github.com/fvigneron/FastPolyEval.

[3] N. Mihalache, F. Vigneron. How to split a tera-polynomial. In preparation.