A vector implementation of the Fast Fourier Transform algorithm

Fornberg, Bengt

doi:10.1090/S0025-5718-81-99783-0

A vector implementation of the Fast Fourier Transform algorithm
HTML articles powered by AMS MathViewer

by Bengt Fornberg PDF

Math. Comp. 36 (1981), 189-191 Request permission

Abstract:

A recent article in this journal by D. G. Korn and J. J. Lambiotte, Jr. discusses implementations of the FFT algorithm on the CDC STAR-100 vector computer. The ’Pease’-algorithm is recommended in cases when only a few transforms can be performed simultaneously. We show how the use of a different algorithm and of trigonometric tables will lead to more than three times faster execution times. The times for large transforms increase only about 39

References

David G. Korn and Jules J. Lambiotte Jr., Computing the fast Fourier transform on a vector computer, Math. Comp. 33 (1979), no. 147, 977–992. MR 528051, DOI 10.1090/S0025-5718-1979-0528051-4
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

IEEE Trans. Audio Electroacoust.

J. Assoc. Comput. Mach.

J. A. Glassman, A generalization of the fast Fourier transform, IEEE Trans. Comput. C-19 (1970), 105–116. MR 253590, DOI 10.1109/t-c.1970.222875
Shmuel Winograd, On computing the discrete Fourier transform, Proc. Nat. Acad. Sci. U.S.A. 73 (1976), no. 4, 1005–1006. MR 415993, DOI 10.1073/pnas.73.4.1005