Fast Approximate Polynomial Multipoint Evaluation and Applications

Authors Alexander Kobel, Michael Sagraloff

Publication date 30 April 2013

Complexity and performance of numerical algorithms (65Y20)

Abstract: It is well known that, using fast algorithms for polynomial multiplication and division, evaluation of a polynomial

F i n m a t h b b C [x]

of degree

n

at

n

complex-valued points can be done with

i l d e O (n)

exact field operations in

m a t h b b C,

where

i l d e O (c d o t)

means that we omit polylogarithmic factors. We complement this result by an analysis of approximate multipoint evaluation of

F

to a precision of

L

bits after the binary point and prove a bit complexity of

i l d e O (n (L + a u + n G a m m a)),

where

2^{a} u

and

2^{G} a m m a,

with

a u, G a m m a i n m a t h b b N_{g e 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 further approximation algorithms which all use polynomial evaluation as a key subroutine. Of these applications, we discuss in detail an algorithm for polynomial interpolation and for computing a Taylor shift of a polynomial. Furthermore, our result can be used to derive improved complexity bounds for algorithms to refine isolating intervals for the real roots of a polynomial. For all of the latter algorithms, we derive near-optimal running times.

This page was built for publication: Fast Approximate Polynomial Multipoint Evaluation and Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6241581)