| Title:
|
Roundoff errors in the fast computation of discrete convolutions (English) |
| Author:
|
Segeth, Karel |
| Language:
|
English |
| Journal:
|
Aplikace matematiky |
| ISSN:
|
0373-6725 |
| Volume:
|
26 |
| Issue:
|
4 |
| Year:
|
1981 |
| Pages:
|
241-262 |
| Summary lang:
|
English |
| Summary lang:
|
Czech |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
discrete convolution |
| Keyword:
|
fast Fourier transform |
| Keyword:
|
analysis of the roundoff errors |
| Keyword:
|
stochastic model |
| MSC:
|
42A15 |
| MSC:
|
65F30 |
| MSC:
|
65T05 |
| MSC:
|
65T40 |
| idZBL:
|
Zbl 0474.65025 |
| idMR:
|
MR0623505 |
| DOI:
|
10.21136/AM.1981.103916 |
| . |
| Date available:
|
2008-05-20T18:17:08Z |
| Last updated:
|
2020-07-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/103916 |
| . |
| Reference:
|
[1] R. Alt: Error propagation in Fourier transforms.Math. Comput. Simulation 20 (1978), 37-43. Zbl 0386.65057, MR 0488922, 10.1016/0378-4754(78)90052-6 |
| Reference:
|
[2] J. W. Cooley J. W. Tukey: An algorithm for the machine calculation of complex Fourier series.Math. Соmр. 19 (1965), 297-301. MR 0178586 |
| Reference:
|
[3] P. J. Davis P. Rabinowitz: Methods of Numerical Integration.Academic Press, New York 1975. MR 0448814 |
| Reference:
|
[4] R. W. Hamming: Numerical Methods for Scientists and Engineers.McGraw-Hill, New York 1962. Zbl 0952.65500, MR 0351023 |
| Reference:
|
[5] D. R. Hartree: Note on systematic roundoff errors in numerical integration.J. Res. Nat. Bur. Standards 42 (1949), 62. MR 0032215 |
| Reference:
|
[6] H. D. Helms: Fast Fourier transform method of computing difference equations and simulating filters.IEEE Trans. Audio Electroacoust. AU-15 (1967), 85-90. 10.1109/TAU.1967.1161905 |
| Reference:
|
[7] P. Henrici: Elements of Numerical Analysis.Wiley, New York 1964. Zbl 0149.10901, MR 0166900 |
| Reference:
|
[8] H. D. Huskey: On the precision of a certain procedure of numerical integration.J. Res. Nat. Bur. Standards 42 (1949), 57-62. MR 0032215, 10.6028/jres.042.005 |
| Reference:
|
[9] L. Jolley: Summation of Series.Chapman and Hall, London 1925. |
| Reference:
|
[10] T. Kaneko B. Liu: Accumulation of round-off error in fast Fourier transforms.J. Assoc. Comput. Mach. 17 (1970), 637-654. MR 0275710, 10.1145/321607.321613 |
| Reference:
|
[11] T. Kaneko B. Liu: On local roundoff errors in floating-point arithmetic.J. Assoc. Comput. Mach. 20 (1973), 391-398. MR 0343577, 10.1145/321765.321771 |
| Reference:
|
[12] G. U. Ramos: Roundoff error analysis of the fast Fourier transform.Math. Соmр. 25 (1971), 757-768., Zbl 0227.65068, MR 0300488 |
| Reference:
|
[13] P. H. Sterbenz: Floating-Point Computation.Prentics-Hall, Englewood Cliffs, N. J., 1974. MR 0349062 |
| Reference:
|
[14] : System/360 Scientific Subroutine Package.IBM Corporation, White Plains, N. Y., 1910. |
| Reference:
|
[15] T. Thong B. Liu: Accumulation of roundoff errors in floating point FFT.IEEE Trans. Circuits and Systems 24 (1977), 132-143. MR 0428702, 10.1109/TCS.1977.1084316 |
| Reference:
|
[16] T. Thong B. Liu: Floating point fast Fourier transform computation using double precision floating point accumulators.ACM Trans. Math. Software 3 (1977), 54-59. MR 0438752, 10.1145/355719.355723 |
| Reference:
|
[17] J. H. Wilkinson: Rounding Errors in Algebraic Processes.HMSO, London 1963. Zbl 1041.65502, MR 0161456 |
| . |
