On computing the discrete Fourier transform
HTML articles powered by AMS MathViewer
- by S. Winograd PDF
- Math. Comp. 32 (1978), 175-199 Request permission
Abstract:
A new algorithm for computing the Discrete Fourier Transform is described. The algorithm is based on a recent result in complexity theory which enables us to derive efficient algorithms for convolution. These algorithms are then used to obtain the new Discrete Fourier Transform algorithm.References
-
S. WINOGRAD, "Some bilinear forms whose multiplicative complexity depends on the field of constants," to be published in Mathematical Systems Theory, Vol. 10.
- 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 C. M. FIDUCCIA & Y. ZALCSTEIN, Algebras Having Linear Multiplicative Complexities, Technical Report 46, Dept. of Computer Science, State University of New York, Stony Brook, August 1975.
- A. L. Toom, The complexity of a scheme of functional elements simulating the multiplication of integers, Dokl. Akad. Nauk SSSR 150 (1963), 496–498 (Russian). MR 0156494 C. M. RADER, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE, v. 5, no. 6, June 1968, pp. 1107-1108.
- I. J. Good, The interaction algorithm and practical Fourier analysis, J. Roy. Statist. Soc. Ser. B 20 (1958), 361–372. MR 102888
Additional Information
- © Copyright 1978 American Mathematical Society
- Journal: Math. Comp. 32 (1978), 175-199
- MSC: Primary 68A10
- DOI: https://doi.org/10.1090/S0025-5718-1978-0468306-4
- MathSciNet review: 0468306