---
_id: '26243'
abstract:
- lang: eng
text: "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."
author:
- first_name: Sven
full_name: Köhler, Sven
last_name: Köhler
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
citation:
ama: 'Köhler S, Ziegler M. On the Stability of Fast Polynomial Arithmetic. In: *Proc.
8th Conference on Real Numbers and Computers*. ; 2008:147-156.'
apa: Köhler, S., & Ziegler, M. (2008). On the Stability of Fast Polynomial Arithmetic.
*Proc. 8th Conference on Real Numbers and Computers*, 147–156.
bibtex: '@inproceedings{Köhler_Ziegler_2008, title={On the Stability of Fast Polynomial
Arithmetic}, booktitle={Proc. 8th Conference on Real Numbers and Computers}, author={Köhler,
Sven and Ziegler, Martin}, year={2008}, pages={147–156} }'
chicago: Köhler, Sven, and Martin Ziegler. “On the Stability of Fast Polynomial
Arithmetic.” In *Proc. 8th Conference on Real Numbers and Computers*, 147–56,
2008.
ieee: S. Köhler and M. Ziegler, “On the Stability of Fast Polynomial Arithmetic,”
in *Proc. 8th Conference on Real Numbers and Computers*, 2008, pp. 147–156.
mla: Köhler, Sven, and Martin Ziegler. “On the Stability of Fast Polynomial Arithmetic.”
*Proc. 8th Conference on Real Numbers and Computers*, 2008, pp. 147–56.
short: 'S. Köhler, M. Ziegler, in: Proc. 8th Conference on Real Numbers and Computers,
2008, pp. 147–156.'
date_created: 2021-10-15T09:57:36Z
date_updated: 2022-01-06T06:57:18Z
department:
- _id: '63'
language:
- iso: eng
page: 147-156
publication: Proc. 8th Conference on Real Numbers and Computers
status: public
title: On the Stability of Fast Polynomial Arithmetic
type: conference
user_id: '15415'
year: '2008'
...