Fast Evaluation of Real and Complex Polynomials
share
We propose an algorithm for quickly evaluating polynomials. It pre-conditions a complex polynomial P of degree d in time O(dlog d), with a low multiplicative constant independent of the precision. Subsequent evaluations of P computed with a fixed precision of p bits are performed in average arithmetic complexity O(√(d(p+log d))) and memory O(dp). The average complexity is computed with respect to points z ∈ℂ, weighted by the spherical area of ℂ. The worst case does not exceed the complexity of Hörner's scheme. In particular, our algorithm performs asymptotically as O(√(dlog d)) per evaluation. For many classes of polynomials, in particular those with random coefficients in a bounded region of ℂ, or for sparse polynomials, our algorithm performs much better than this upper bound, without any modification or parameterization.The article 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 [MV22].Our claims regarding complexity and accuracy are confirmed in practice by a set of comprehensive benchmarks.
READ FULL TEXT