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 Library locked




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:


Abstract, Links, (C)

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},
ADDRESS = {Ithaca, NY},
MONTH = {April},
}


Entry last modified by Alexander Kobel, 02/17/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/14/2014 04:06:18 PM
Revision
0.



Editor
Alexander Kobel



Edit Date
01/14/2014 04:06:18 PM