A stochastic roundoff error analysis for the convolution
HTML articles powered by AMS MathViewer
- by Daniela Calvetti PDF
- Math. Comp. 59 (1992), 569-582 Request permission
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
- 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, DOI 10.1002/0471722235
- Daniela Calvetti, A stochastic roundoff error analysis for the fast Fourier transform, Math. Comp. 56 (1991), no. 194, 755–774. MR 1068824, DOI 10.1090/S0025-5718-1991-1068824-0
- 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
- Peter Henrici, Error propagation for difference method, John Wiley & Sons, Inc., New York-London, 1963. MR 0154416 —, Essentials of numerical analysis, Wiley, New York, 1982.
- 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
- 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 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.
- George U. Ramos, Roundoff error analysis of the fast Fourier transform, Math. Comp. 25 (1971), 757–768. MR 300488, DOI 10.1090/S0025-5718-1971-0300488-0
- F. Stummel, Perturbation theory for evaluation algorithms of arithmetic expressions, Math. Comp. 37 (1981), no. 156, 435–473. MR 628707, DOI 10.1090/S0025-5718-1981-0628707-8
- Friedrich Stummel and Karl Hainer, Praktische Mathematik, 2nd ed., Teubner Studienbücher Mathematik. [Teubner Mathematical Textbooks], B. G. Teubner, Stuttgart, 1982 (German). MR 660252 C. J. Weinstein, Roundoff noise in floating point fast Fourier transform computation, IEEE Trans. Audio Electroacoust. 17 (1969), 209-215. P. D. Welsh, A fixed-point fast Fourier transform error analysis, IEEE Trans. Audio Electroacoust. 17 (1969), 151-157.
- J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Math. Comp. 59 (1992), 569-582
- MSC: Primary 65G05; Secondary 44A35, 65T20
- DOI: https://doi.org/10.1090/S0025-5718-1992-1134719-8
- MathSciNet review: 1134719