Roundoff error analysis of the fast Fourier transform
HTML articles powered by AMS MathViewer
- by George U. Ramos PDF
- Math. Comp. 25 (1971), 757-768 Request permission
Abstract:
This paper presents an analysis of roundoff errors occurring in the floating-point computation of the fast Fourier transform. Upper bounds are derived for the ratios of the root-mean-square (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.References
-
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. 563-578.
P. D. Welch, “A fixed-point fast Fourier transform error analysis,” IEEE Trans. Audio and Electroacoustics, v. AU-17, 1969, pp. 151-157.
C. J. Weinstein, “Roundoff noise in floating point fast Fourier transform computation,” IEEE Trans. Audio and Electroacoustics, v. AU-17, 1969, pp. 209-215.
- Toyohisa Kaneko and Bede Liu, Accumulation of round-off error in fast Fourier transforms, J. Assoc. Comput. Mach. 17 (1970), 637–654. MR 275710, DOI 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 10.1090/S0025-5718-1965-0178586-1 W. M. Gentleman, “Matrix multiplication and fast Fourier transforms,” Bell System Tech. J., v. 47, 1968, pp. 1099-1103.
- Richard C. Singleton, On computing the fast Fourier transform, Comm. ACM 10 (1967), 647–654. MR 0241017, DOI 10.1145/363717.363771 F. Theilheimer, “A matrix version of the fast Fourier transform,” IEEE Trans. Audio and Electroacoustics, v. AU-17, 1969, pp. 158-161. D. K. Kahaner, Matrix Description of the Fast Fourier Transform, Los Alamos Scientific Laboratory Report LA-4275-MS, 1969.
- J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
- Eugene Isaacson and Herbert Bishop Keller, Analysis of numerical methods, John Wiley & Sons, Inc., New York-London-Sydney, 1966. MR 0201039 N. M. Brenner, Three FORTRAN Programs that Perform the Cooley-Tukey Fourier Transform, Technical Note 1967-2, 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. AU-17, 1969, pp. 93-103. M. C. Pease, “An adaptation of the fast Fourier transform for parallel processing,” J. ACM, v. 15, 1968, pp. 252-264.
- I. J. Good, The interaction algorithm and practical Fourier analysis, J. Roy. Statist. Soc. Ser. B 20 (1958), 361–372. MR 102888
Additional Information
- © Copyright 1971 American Mathematical Society
- Journal: Math. Comp. 25 (1971), 757-768
- MSC: Primary 65T05
- DOI: https://doi.org/10.1090/S0025-5718-1971-0300488-0
- MathSciNet review: 0300488