English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Fast Approximate Polynomial Multipoint Evaluation and Applications

MPS-Authors
/persons/resource/persons44806

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

/persons/resource/persons45332

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)

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.