---
res:
bibo_abstract:
- "Operations on univariate dense polynomials—multiplication, division with remainder,
multipoint\r\nevaluation—constitute central primitives entering as build-up blocks
into many higher applications and\r\nalgorithms. Fast Fourier Transform permits
to accelerate them from naive quadratic to running time\r\nO(n·polylogn), that
is softly linear in the degree n of the input. This is routinely employed in complexity\r\ntheoretic
considerations and, over integers and finite fields, in practical number theoretic
calculations.\r\nThe present work explores the benefit of fast polynomial arithmetic
over the field of real numbers\r\nwhere the precision of approximation becomes
crucial. To this end, we study the computability of the\r\nabove operations in
the sense of Recursive Analysis as an effective refinement of continuity. This
theo-\r\nretical worst-case stability analysis is then complemented by an empirical
evaluation: We use GMP and\r\nthe iRRAM to find the precision required for the
intermediate calculations in order to achieve a desired\r\noutput accuracy.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sven
foaf_name: Köhler, Sven
foaf_surname: Köhler
- foaf_Person:
foaf_givenName: Martin
foaf_name: Ziegler, Martin
foaf_surname: Ziegler
dct_date: 2008^xs_gYear
dct_language: eng
dct_title: On the Stability of Fast Polynomial Arithmetic@
...