hide
Free keywords:
Computer Science, Numerical Analysis, cs.NA,Computer Science, Symbolic Computation, cs.SC,Mathematics, Numerical Analysis, math.NA,
Abstract:
It is well known that, using fast algorithms for polynomial multiplication
and division, evaluation of a polynomial $F\in\CC[x]$ of degree $n$ at $n$
complex-valued points can be done with $\softOh(n)$ exact field operations in
$\CC,$ where $\softOh(\cdot)$ means that we omit polylogarithmic factors. We
complement this result by an analysis of \emph{approximate multipoint
evaluation} of $F$ to a precision of $L$ bits after the binary point and prove
a bit complexity of $\softOh (n(L + \tau + n\Gamma)),$ where $2^\tau$ and
$\cramped{2^{\Gamma}},$ with $\tau,\Gamma\in\NN_{\ge 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 three further approximation algorithms which all use
polynomial evaluation as a key subroutine. This comprises an algorithm to
approximate the real roots of a polynomial, an algorithm for polynomial
interpolation, and a method for computing a Taylor shift of a polynomial. For
all of the latter algorithms, we derive near optimal running times.
