Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Roundoff error analysis of the fast Fourier transform


Author: George U. Ramos
Journal: Math. Comp. 25 (1971), 757-768
MSC: Primary 65T05
MathSciNet review: 0300488
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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.
  • [2] P. D. Welch, ``A fixed-point fast Fourier transform error analysis,'' IEEE Trans. Audio and Electroacoustics, v. AU-17, 1969, pp. 151-157.
  • [3] C. J. Weinstein, ``Roundoff noise in floating point fast Fourier transform computation,'' IEEE Trans. Audio and Electroacoustics, v. AU-17, 1969, pp. 209-215.
  • [4] Toyohisa Kaneko and Bede Liu, Accumulation of round-off error in fast Fourier transforms, J. Assoc. Comput. Mach. 17 (1970), 637–654. MR 0275710 (43 #1463)
  • [5] James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301. MR 0178586 (31 #2843), http://dx.doi.org/10.1090/S0025-5718-1965-0178586-1
  • [6] W. M. Gentleman, ``Matrix multiplication and fast Fourier transforms,'' Bell System Tech. J., v. 47, 1968, pp. 1099-1103.
  • [7] Richard C. Singleton, On computing the fast Fourier transform, Comm. ACM 10 (1967), 647–654. MR 0241017 (39 #2362)
  • [8] F. Theilheimer, ``A matrix version of the fast Fourier transform,'' IEEE Trans. Audio and Electroacoustics, v. AU-17, 1969, pp. 158-161.
  • [9] D. K. Kahaner, Matrix Description of the Fast Fourier Transform, Los Alamos Scientific Laboratory Report LA-4275-MS, 1969.
  • [10] J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456 (28 #4661)
  • [11] Eugene Isaacson and Herbert Bishop Keller, Analysis of numerical methods, John Wiley & Sons, Inc., New York-London-Sydney, 1966. MR 0201039 (34 #924)
  • [12] 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.
  • [13] 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.
  • [14] M. C. Pease, ``An adaptation of the fast Fourier transform for parallel processing,'' J. ACM, v. 15, 1968, pp. 252-264.
  • [15] I. J. Good, The interaction algorithm and practical Fourier analysis, J. Roy. Statist. Soc. Ser. B 20 (1958), 361–372. MR 0102888 (21 #1674)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65T05

Retrieve articles in all journals with MSC: 65T05


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1971-0300488-0
PII: S 0025-5718(1971)0300488-0
Keywords: Fast Fourier transform, floating-point, roundoff errors
Article copyright: © Copyright 1971 American Mathematical Society