Roundoff errors in the fast computation of discrete convolutions

Karel Segeth

Aplikace matematiky (1981)

  • Volume: 26, Issue: 4, page 241-262
  • ISSN: 0862-7940

Abstract

top
The efficient evaluation of a discrete convolution is usually carried out as a repated evaluation of a discrete convolution of a special type with the help of the fast Fourier transform. The paper is concerned with the analysis of the roundoff errors in the fast computation of this convolution. To obtain a comparison, the roundoff errors in the usual (direct) computation of this convolution are also considered. A stochastic model of the propagation of roundoff errors. is employed. The theoretical results are compared with the actual roundoff errors is employed. The theoretical results are compared with the actual roundoff errors occurring in the evaluation of a simple model discrete convolution.

How to cite

top

Segeth, Karel. "Roundoff errors in the fast computation of discrete convolutions." Aplikace matematiky 26.4 (1981): 241-262. <http://eudml.org/doc/15199>.

@article{Segeth1981,
abstract = {The efficient evaluation of a discrete convolution is usually carried out as a repated evaluation of a discrete convolution of a special type with the help of the fast Fourier transform. The paper is concerned with the analysis of the roundoff errors in the fast computation of this convolution. To obtain a comparison, the roundoff errors in the usual (direct) computation of this convolution are also considered. A stochastic model of the propagation of roundoff errors. is employed. The theoretical results are compared with the actual roundoff errors is employed. The theoretical results are compared with the actual roundoff errors occurring in the evaluation of a simple model discrete convolution.},
author = {Segeth, Karel},
journal = {Aplikace matematiky},
keywords = {discrete convolution; fast Fourier transform; analysis of the roundoff errors; stochastic model; discrete convolution; fast Fourier transform; analysis of the roundoff errors; stochastic model},
language = {eng},
number = {4},
pages = {241-262},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Roundoff errors in the fast computation of discrete convolutions},
url = {http://eudml.org/doc/15199},
volume = {26},
year = {1981},
}

TY - JOUR
AU - Segeth, Karel
TI - Roundoff errors in the fast computation of discrete convolutions
JO - Aplikace matematiky
PY - 1981
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 26
IS - 4
SP - 241
EP - 262
AB - The efficient evaluation of a discrete convolution is usually carried out as a repated evaluation of a discrete convolution of a special type with the help of the fast Fourier transform. The paper is concerned with the analysis of the roundoff errors in the fast computation of this convolution. To obtain a comparison, the roundoff errors in the usual (direct) computation of this convolution are also considered. A stochastic model of the propagation of roundoff errors. is employed. The theoretical results are compared with the actual roundoff errors is employed. The theoretical results are compared with the actual roundoff errors occurring in the evaluation of a simple model discrete convolution.
LA - eng
KW - discrete convolution; fast Fourier transform; analysis of the roundoff errors; stochastic model; discrete convolution; fast Fourier transform; analysis of the roundoff errors; stochastic model
UR - http://eudml.org/doc/15199
ER -

References

top
  1. R. Alt, 10.1016/0378-4754(78)90052-6, Math. Comput. Simulation 20 (1978), 37-43. (1978) Zbl0386.65057MR0488922DOI10.1016/0378-4754(78)90052-6
  2. J. W. Cooley J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Соmр. 19 (1965), 297-301. (1965) MR0178586
  3. P. J. Davis P. Rabinowitz, Methods of Numerical Integration, Academic Press, New York 1975. (1975) MR0448814
  4. R. W. Hamming, Numerical Methods for Scientists and Engineers, McGraw-Hill, New York 1962. (1962) Zbl0952.65500MR0351023
  5. D. R. Hartree, Note on systematic roundoff errors in numerical integration, J. Res. Nat. Bur. Standards 42 (1949), 62. (1949) MR0032215
  6. H. D. Helms, 10.1109/TAU.1967.1161905, IEEE Trans. Audio Electroacoust. AU-15 (1967), 85-90. (1967) DOI10.1109/TAU.1967.1161905
  7. P. Henrici, Elements of Numerical Analysis, Wiley, New York 1964. (1964) Zbl0149.10901MR0166900
  8. H. D. Huskey, 10.6028/jres.042.005, J. Res. Nat. Bur. Standards 42 (1949), 57-62. (1949) MR0032215DOI10.6028/jres.042.005
  9. L. Jolley, Summation of Series, Chapman and Hall, London 1925. (1925) 
  10. T. Kaneko B. Liu, 10.1145/321607.321613, J. Assoc. Comput. Mach. 17 (1970), 637-654. (1970) MR0275710DOI10.1145/321607.321613
  11. T. Kaneko B. Liu, 10.1145/321765.321771, J. Assoc. Comput. Mach. 20 (1973), 391-398. (1973) MR0343577DOI10.1145/321765.321771
  12. G. U. Ramos, Roundoff error analysis of the fast Fourier transform, Math. Соmр. 25 (1971), 757-768., (1971) Zbl0227.65068MR0300488
  13. P. H. Sterbenz, Floating-Point Computation, Prentics-Hall, Englewood Cliffs, N. J., 1974. (1974) MR0349062
  14. System/360 Scientific Subroutine Package, IBM Corporation, White Plains, N. Y., 1910. (1910) 
  15. T. Thong B. Liu, 10.1109/TCS.1977.1084316, IEEE Trans. Circuits and Systems 24 (1977), 132-143. (1977) MR0428702DOI10.1109/TCS.1977.1084316
  16. T. Thong B. Liu, 10.1145/355719.355723, ACM Trans. Math. Software 3 (1977), 54-59. (1977) MR0438752DOI10.1145/355719.355723
  17. J. H. Wilkinson, Rounding Errors in Algebraic Processes, HMSO, London 1963. (1963) Zbl1041.65502MR0161456

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.