# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Fast Approximate Polynomial Multipoint Evaluation and Applications

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1304.8069.pdf

(Preprint), 451KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Kobel, A., & Sagraloff, M. (2013). Fast Approximate Polynomial Multipoint Evaluation and Applications. Retrieved from http://arxiv.org/abs/1304.8069.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0015-8658-2

##### 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.