Note: |
|
(LaTeX) Abstract: |
It is well known that, using fast algorithms for polynomial multiplication and division, evaluation of a polynomial $F\in\mathbb{C}[x]$ of degree $n$ at $n$ complex-valued points can be done with $\tilde{O}(n)$ exact field operations in $\mathbb{C},$ where $\tilde{O}(\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 $\tilde{O} (n(L + \tau + n\Gamma)),$ where $2^\tau$ and $2^\Gamma,$ with $\tau, \Gamma \in \mathbb{N}_{\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. |
URL for the Abstract: |
|
Categories / Keywords: |
approximate arithmetic, fast arithmetic, multipoint evaluation, certified computation, polynomial division, root refinement, Taylor shift, polynomial interpolation |
HyperLinks / References / URLs: |
|
Copyright Message: |
|
Personal Comments: |
|
Download
Access Level: |
Internal |
|
Edit History (please click the blue arrow to see the details)