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
DOI: https://doi.org/10.1090/S0025-5718-1991-1068824-0
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] Ramesh C. Agarwal and James W. Cooley, Fourier transform and convolution subroutines for the IBM 3090 Vector Facility, IBM J. Res. Develop. 30 (1986), no. 2, 145–162. MR 840342, https://doi.org/10.1147/rd.302.0145
  • [2] Steven F. Arnold, The theory of linear models and multivariate analysis, John Wiley & Sons, Inc., New York, 1981. Wiley Series in Probability and Mathematical Statistics. MR 606011
  • [3] Peter Bloomfield, Fourier analysis of time series, 2nd ed., Wiley Series in Probability and Statistics: Applied Probability and Statistics, Wiley-Interscience [John Wiley & Sons], New York, 2000. An introduction. MR 1884963
  • [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] 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, https://doi.org/10.1090/S0025-5718-1965-0178586-1
  • [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] Peter Henrici, Discrete variable methods in ordinary differential equations, John Wiley & Sons, Inc., New York-London, 1962. MR 0135729
  • [12] Peter Henrici, A model for the propagation of rounding error in floating arithmetic, Interval mathematics, 1980 (Freiburg, 1980) Academic Press, New York-London, 1980, pp. 49–73. MR 651358
  • [13] Peter Henrici, Essentials of numerical analysis with pocket calculator demonstrations, John Wiley & Sons, Inc., New York, 1982. MR 655251
  • [14] Peter Henrici, Applied and computational complex analysis. Vol. 3, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1986. Discrete Fourier analysis—Cauchy integrals—construction of conformal maps—univalent functions; A Wiley-Interscience Publication. MR 822470
  • [15] Toyohisa Kaneko and Bede Liu, Accumulation of round-off error in fast Fourier transforms, J. Assoc. Comput. Mach. 17 (1970), 637–654. MR 0275710, https://doi.org/10.1145/321607.321613
  • [16] Gerhard Merz, Fast Fourier transform algorithms with applications, Computational aspects of complex analysis (Braunlage, 1982) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 102, Reidel, Dordrecht, 1983, pp. 249–278. MR 712899
  • [17] George U. Ramos, Roundoff error analysis of the fast Fourier transform, Math. Comp. 25 (1971), 757–768. MR 0300488, https://doi.org/10.1090/S0025-5718-1971-0300488-0
  • [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] Friedrich Stummel and Karl Hainer, Praktische Mathematik, 2nd ed., B. G. Teubner, Stuttgart, 1982 (German). Teubner Studienbücher Mathematik. [Teubner Mathematical Textbooks]. MR 660252
  • [21] Clive Temperton, Self-sorting mixed-radix fast Fourier transforms, J. Comput. Phys. 52 (1983), no. 1, 1–23. MR 725591, https://doi.org/10.1016/0021-9991(83)90013-X
  • [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, Inc., Englewood Cliffs, N.J., 1963. MR 0161456

Similar Articles

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

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


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1991-1068824-0
Keywords: Accompanying linear forms, floating-point arithmetic, Radix-2 Fast Fourier Transform, rounding errors, random variables
Article copyright: © Copyright 1991 American Mathematical Society