Fast Evaluation of Real and Complex Polynomials

Ramona Anton, Nicolae Mihalache, François Vigneron

We propose an algorithm for quickly evaluating polynomials. It pre-conditions a complex polynomial $P$ of degree $d$ in time $O(d\log d)$, with a low multiplicative constant indepe…