Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Fast Approximate Polynomial Multipoint Evaluation and Applications


Kobel,  Alexander
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Sagraloff,  Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 451KB

Supplementary Material (public)
There is no public supplementary material available

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