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 convolution

Author: Daniela Calvetti
Journal: Math. Comp. 59 (1992), 569-582
MSC: Primary 65G05; Secondary 44A35, 65T20
MathSciNet review: 1134719
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the accuracy of an algorithm which computes the convolution via Radix-2 fast Fourier transforms. Upper bounds are derived for 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. These results are compared with the corresponding ones for two algorithms computing the convolution directly, via Horner's sums and using cascade summation, respectively.

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

  • [1] P. Bloomfield, Fourier analysis of time series, Wiley, New York, 1976. MR 1884963 (2002k:62006)
  • [2] D. Calvetti, A stochastic roundoff error analysis for the fast Fourier transform, Math. Comp. 56 (1991), 755-774. MR 1068824 (91m:65341)
  • [3] 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)
  • [4] P. Henrici, Error propagation for difference methods, Wiley, New York, 1963. MR 0154416 (27:4365)
  • [5] -, Essentials of numerical analysis, Wiley, New York, 1982.
  • [6] -, Applied and computational complex analysis, Vol. 3, Wiley, New York, 1986. MR 822470 (87h:30002)
  • [7] T. Kaneko and B. Liu, Accumulation of roundoff error in fast Fourier transforms, J. Assoc. Comput. Mach. 17 (1970), 637-654. MR 0275710 (43:1463)
  • [8] A. Oppenheim and C. Weinstein, A bound on the output of a circular convolution with application to digital filtering, Trans. Audio Electroacoust. 17 (1969), 120-124.
  • [9] G. U. Ramos, Roundoff error analysis of the fast Fourier transform, Math. Comp. 25 (1971), 757-768. MR 0300488 (45:9534)
  • [10] F. Stummel, Perturbation theory for evaluation algorithms of arithmetic expressions, Math. Comp. 37 (1981), 435-473. MR 628707 (82i:65032)
  • [11] F. Stummel and K. Heiner, Praktische Mathematik, 2nd ed., Teubner, Stuttgart, 1982. MR 660252 (83f:00008)
  • [12] C. J. Weinstein, Roundoff noise in floating point fast Fourier transform computation, IEEE Trans. Audio Electroacoust. 17 (1969), 209-215.
  • [13] P. D. Welsh, A fixed-point fast Fourier transform error analysis, IEEE Trans. Audio Electroacoust. 17 (1969), 151-157.
  • [14] J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Englewood Cliffs, NJ, 1963. MR 0161456 (28:4661)

Similar Articles

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

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

Additional Information

Keywords: Accompanying linear forms, floating-point arithmetic, Radix-2 fast Fourier transform, convolution, rounding errors, random variables
Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society