A stochastic roundoff error analysis for the convolution

Calvetti, Daniela

doi:10.1090/S0025-5718-1992-1134719-8

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

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 bound on the output of a circular convolution with application to digital filtering

17

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

Roundoff noise in floating point fast Fourier transform computation

17

A fixed-point fast Fourier transform error analysis

17

J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456