A Stochastic Roundoff Error Analysis for the Fast Fourier Transform
- 1 April 1991
- journal article
- Published by JSTOR in Mathematics of Computation
- Vol. 56 (194) , 755-774
- https://doi.org/10.2307/2008406
Abstract
We study the accuracy of the output of the Fast Fourier Transform by estimating the expected value and the variance of the accompanying linear forms in terms of the expected value and variance of the relative roundoff errors for the elementary operations of addition and multiplication. We compare the results with the corresponding ones for the direct algorithm for the Discrete Fourier Transform, and we give indications of the relative performances when different rounding schemes are used. We also present the results of numerical experiments run to test the theoretical bounds and discuss their significance.Keywords
This publication has 9 references indexed in Scilit:
- Fourier Analysis of Time SeriesWiley Series in Probability and Statistics, 2000
- Fourier transform and convolution subroutines for the IBM 3090 Vector FacilityIBM Journal of Research and Development, 1986
- Self-sorting mixed-radix fast Fourier transformsJournal of Computational Physics, 1983
- Fast Fourier Transform Algorithms with ApplicationsPublished by Springer Nature ,1983
- Praktische MathematikPublished by Springer Nature ,1982
- A MODEL FOR THE PROPAGATION OF ROUNDING ERROR IN FLOATING ARITHMETICPublished by Elsevier ,1980
- Roundoff Error Analysis of the Fast Fourier TransformMathematics of Computation, 1971
- Accumulation of Round-Off Error in Fast Fourier TransformsJournal of the ACM, 1970
- An Algorithm for the Machine Calculation of Complex Fourier SeriesMathematics of Computation, 1965