Roundoff error analysis of the fast Fourier transform
Author:
George U. Ramos
Journal:
Math. Comp. 25 (1971), 757768
MSC:
Primary 65T05
DOI:
https://doi.org/10.1090/S00255718197103004880
MathSciNet review:
0300488
Fulltext PDF Free Access
Abstract  References  Similar Articles  Additional Information
Abstract: This paper presents an analysis of roundoff errors occurring in the floatingpoint computation of the fast Fourier transform. Upper bounds are derived for the ratios of the rootmeansquare (RMS) and maximum roundoff errors in the output data to the RMS value of the output data for both single and multidimensional transformations. These bounds are compared experimentally with actual roundoff errors.

W. M. Gentleman & G. Sande, Fast Fourier Transforms—For Fun and Profit, Fall Joint Computer Conference AFIPS Proc., 1966, v. 29, Spartan, Washington, D.C., 1966, pp. 563578.
P. D. Welch, “A fixedpoint fast Fourier transform error analysis,” IEEE Trans. Audio and Electroacoustics, v. AU17, 1969, pp. 151157.
C. J. Weinstein, “Roundoff noise in floating point fast Fourier transform computation,” IEEE Trans. Audio and Electroacoustics, v. AU17, 1969, pp. 209215.
 Toyohisa Kaneko and Bede Liu, Accumulation of roundoff error in fast Fourier transforms, J. Assoc. Comput. Mach. 17 (1970), 637–654. MR 275710, DOI https://doi.org/10.1145/321607.321613
 James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301. MR 178586, DOI https://doi.org/10.1090/S00255718196501785861 W. M. Gentleman, “Matrix multiplication and fast Fourier transforms,” Bell System Tech. J., v. 47, 1968, pp. 10991103.
 Richard C. Singleton, On computing the fast Fourier transform, Comm. ACM 10 (1967), 647–654. MR 0241017, DOI https://doi.org/10.1145/363717.363771 F. Theilheimer, “A matrix version of the fast Fourier transform,” IEEE Trans. Audio and Electroacoustics, v. AU17, 1969, pp. 158161. D. K. Kahaner, Matrix Description of the Fast Fourier Transform, Los Alamos Scientific Laboratory Report LA4275MS, 1969.
 J. H. Wilkinson, Rounding errors in algebraic processes, PrenticeHall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
 Eugene Isaacson and Herbert Bishop Keller, Analysis of numerical methods, John Wiley & Sons, Inc., New YorkLondonSydney, 1966. MR 0201039 N. M. Brenner, Three FORTRAN Programs that Perform the CooleyTukey Fourier Transform, Technical Note 19672, M.I.T. Lincoln Lab., Lexington, Mass., 1967. R. C. Singleton, “An algorithm for computing the mixed radix fast Fourier transform,” IEEE Trans. Audio and Electroacoustics, v. AU17, 1969, pp. 93103. M. C. Pease, “An adaptation of the fast Fourier transform for parallel processing,” J. ACM, v. 15, 1968, pp. 252264.
 I. J. Good, The interaction algorithm and practical Fourier analysis, J. Roy. Statist. Soc. Ser. B 20 (1958), 361–372. MR 102888
Retrieve articles in Mathematics of Computation with MSC: 65T05
Retrieve articles in all journals with MSC: 65T05
Additional Information
Keywords:
Fast Fourier transform,
floatingpoint,
roundoff errors
Article copyright:
© Copyright 1971
American Mathematical Society