Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A stochastic roundoff error analysis for the fast Fourier transform

Author: Daniela Calvetti
Journal: Math. Comp. 56 (1991), 755-774
MSC: Primary 65T20; Secondary 65G05
MathSciNet review: 1068824
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

  • [1] R. C. Agarwal and J. W. Cooley, Fourier transform and convolution subroutines for the IBM 3090 Vector Facility, IBM J. Res. Develop. 30 (1986), 145-162. MR 840342
  • [2] S. Arnold, The theory of linear models and multivariate analysis, Wiley, New York, 1981. MR 606011 (82g:62001)
  • [3] P. Bloomfield, Fourier analysis of time series, Wiley, New York, 1976. MR 1884963 (2002k:62006)
  • [4] D. Calvetti, A stochastic roundoff error analysis for the FFT, Doctoral Dissertation, University of North Carolina at Chapel Hill, 1989.
  • [5] J. W. R. Cooley, A. W. Lewis, and P. D. Welsh, The Fast Fourier Transform and its applications, Research Paper Rc-1743, IBM Research, 1967.
  • [6] -, The Fast Fourier Transform algorithm: Programming considerations in the calculation of sine, cosine, and Laplace transforms, J. Sound Vibration 12 (1970), 315-337.
  • [7] J. W. R. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297-301. MR 0178586 (31:2843)
  • [8] C. de Boor, FFT as nested multiplication with a twist, SIAM J. Sci. Statist. Comput. 1 (1980), 173-178.
  • [9] W. Gander and A. Mazzario, Numerische Prozeduren. I (in memoriam Heinz Rutishauser), Ber. Fachgruppe Comput. Wiss., vol. 4, ETH, Zurich, 1972.
  • [10] W. M. Gentleman and G. Sande, Fast Fourier Transforms--For fun and profit, Fall Joint Computer Conf., AFIPS Proc., vol. 29, Spartan, Washington, D. C., 1966, pp. 563-578.
  • [11] P. Henrici, Discrete variable methods in ordinary differential equations, Wiley, New York, 1962. MR 0135729 (24:B1772)
  • [12] -, A model for the propagation of rounding error in floating arithmetic, Interval Mathematics, 1980 (Karl L. E. Nickel, ed.), Academic Press, New York, 1980, pp. 49-73. MR 651358 (83c:65093)
  • [13] -, Essentials of numerical analysis with pocket calculator demonstrations, Wiley, New York, 1982. MR 655251 (83h:65002)
  • [14] -, Applied and computational complex analysis, vol. 3, Wiley, New York, 1986. MR 822470 (87h:30002)
  • [15] T. Kanero and B. Liu, Accumulation of roundoff error in fast Fourier transforms, J. Assoc. Comput. Mach. 17 (1970), 637-654. MR 0275710 (43:1463)
  • [16] G. Merz, Fast Fourier transform algorithm with applications, Computational Aspects of Complex Analysis (H. Werner et al., eds.), Reidel, Dordrecht, 1983, pp. 249-278. MR 712899 (85g:65128)
  • [17] G. U. Ramos, Roundoff error analysis of the Fast Fourier Transform, Math. Comp. 25 (1971), 757-768. MR 0300488 (45:9534)
  • [18] R. C. Singleton, Algorithm 339. An Algol procedure for the Fast Fourier Transform with arbitrary factors, Comm. ACM 11 (1968), 776.
  • [19] F. Stummel, Forward error analysis of Gaussian elimination, Numer. Math. 46 (1985), 365-395; 397-415.
  • [20] F. Stummel and K. Heiner, Praktische Mathematik, 2nd ed., Teubner, Stuttgart, 1982. MR 660252 (83f:00008)
  • [21] C. Temperton, Self-sorting mixed radix Fast Fourier Transforms, J. Comput. Phys. 52 (1983), 1-23. MR 725591 (84k:86001)
  • [22] M. L. Uhrich, Fast Fourier Transform without sorting, IEEE Trans. Audio Electroacoust. 17 (1969), 170-172.
  • [23] P. D. Welsh, A fixed-point fast Fourier transform error analysis, IEEE Trans. Audio Electroacoust. 17 (1969), 151-157.
  • [24] C. J. Weinstein, Roundoff noise in floating point fast Fourier transform computation, IEEE Trans. Audio Electroacoust. 17 (1969), 209-215.
  • [25] J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Englewood Cliffs, N. J., 1963. MR 0161456 (28:4661)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65T20, 65G05

Retrieve articles in all journals with MSC: 65T20, 65G05

Additional Information

Keywords: Accompanying linear forms, floating-point arithmetic, Radix-2 Fast Fourier Transform, rounding errors, random variables
Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society