2013/04/30 by Kobel, Alexander, Sagraloff, Michael
#65Y20 #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #G.1.0 #Numerical Analysis (math.NA) #Symbolic Computation (cs.SC)
paper · doi:10.48550/arxiv.1304.8069
It is well known that, using fast algorithms for polynomial multiplication and division, evaluation of a polynomial F ∈ ℂ[x] of degree n at n complex-valued points can be done with O(n) exact field operations in ℂ, where O(⋅) means that we omit polylogarithmic factors. We complement this result by an analysis of approximate multipoint evaluation of F to a precision of L bits after the binary point and prove a bit complexity of O(n(L + τ+ nΓ)), where 2τ and 2Γ, with τ, Γ∈ ℕ≥ 1, are bounds on the magnitude of the coefficients of F and the evaluation points, respectively. In particular, in the important case where the precision demand dominates the other input parameters, the complexity is soft-linear in n and L. Our result on approximate multipoint evaluation has some interesting consequences on the bit complexity of further approximation algorithms which all use polynomial evaluation as a key subroutine. Of these applications, we discuss in detail an algorithm for polynomial interpolation and for computing a Taylor shift of a polynomial. Furthermore, our result can be used to derive improved complexity bounds for algorithms to refine isolating intervals for the real roots of a polynomial. For all of the latter algorithms, we derive near-optimal running times.