conference paper
On the Stability of Fast Polynomial Arithmetic
Sven
Köhler
author
Martin
Ziegler
author
63
department
Operations on univariate dense polynomials—multiplication, division with remainder, multipoint
evaluation—constitute central primitives entering as build-up blocks into many higher applications and
algorithms. Fast Fourier Transform permits to accelerate them from naive quadratic to running time
O(n·polylogn), that is softly linear in the degree n of the input. This is routinely employed in complexity
theoretic considerations and, over integers and finite fields, in practical number theoretic calculations.
The present work explores the benefit of fast polynomial arithmetic over the field of real numbers
where the precision of approximation becomes crucial. To this end, we study the computability of the
above operations in the sense of Recursive Analysis as an effective refinement of continuity. This theo-
retical worst-case stability analysis is then complemented by an empirical evaluation: We use GMP and
the iRRAM to find the precision required for the intermediate calculations in order to achieve a desired
output accuracy.
2008
eng
Proc. 8th Conference on Real Numbers and Computers
147-156
@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} }
Köhler, Sven, and Martin Ziegler. “On the Stability of Fast Polynomial Arithmetic.” <i>Proc. 8th Conference on Real Numbers and Computers</i>, 2008, pp. 147–56.
S. Köhler and M. Ziegler, “On the Stability of Fast Polynomial Arithmetic,” in <i>Proc. 8th Conference on Real Numbers and Computers</i>, 2008, pp. 147–156.
Köhler, Sven, and Martin Ziegler. “On the Stability of Fast Polynomial Arithmetic.” In <i>Proc. 8th Conference on Real Numbers and Computers</i>, 147–56, 2008.
Köhler, S., & Ziegler, M. (2008). On the Stability of Fast Polynomial Arithmetic. <i>Proc. 8th Conference on Real Numbers and Computers</i>, 147–156.
Köhler S, Ziegler M. On the Stability of Fast Polynomial Arithmetic. In: <i>Proc. 8th Conference on Real Numbers and Computers</i>. ; 2008:147-156.
S. Köhler, M. Ziegler, in: Proc. 8th Conference on Real Numbers and Computers, 2008, pp. 147–156.
262432021-10-15T09:57:36Z2022-01-06T06:57:18Z