Electronic Journal Article @Article Zeitschriftenartikel in einem e-Journal

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Kobel, Alexander Sagraloff, Michael dblp dblp
 BibTeX cite key*: DBLP:journals/corr/abs-1304-8069

 Title
 Title*: Fast Approximate Polynomial Multipoint Evaluation and Applications

 Journal
 Journal Title*: arXiv Journal's URL: http://arxiv.org/ Download URL for the article: http://arxiv.org/abs/1304.8069 Language: English

 Publisher
 Publisher's Name: Cornell University Library Publisher's URL: http://www.cornell.edu/ Publisher's Address: Ithaca, NY ISSN:

 Vol, No, Year, pp.
 Volume: abs/1304.8069 Number: Month: April Year*: 2013 Pages: 17 Number of VG Pages: 17 Sequence Number: DOI:

 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

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group MPG Subsubunit: Geometry, Topology, and Algebra Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@MISC{DBLP:journals/corr/abs-1304-8069,
AUTHOR = {Kobel, Alexander and Sagraloff, Michael},
TITLE = {Fast Approximate Polynomial Multipoint Evaluation and Applications},
JOURNAL = {arXiv},
PUBLISHER = {Cornell University Library},
YEAR = {2013},
VOLUME = {abs/1304.8069},
PAGES = {17},