A vector implementation of the Fast Fourier Transform algorithm
Author:
Bengt Fornberg
Journal:
Math. Comp. 36 (1981), 189191
MSC:
Primary 68A10; Secondary 42A68
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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 STAR100 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
 [1]
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
(80k:65108), http://dx.doi.org/10.1090/S00255718197905280514
 [2]
James
W. Cooley and John
W. Tukey, An algorithm for the machine
calculation of complex Fourier series, Math.
Comp. 19 (1965),
297–301. MR 0178586
(31 #2843), http://dx.doi.org/10.1090/S00255718196501785861
 [3]
W. T. Cochran et al., "What is the Fast Fourier Transform?," IEEE Trans. Audio Electroacoust., v. Au15, 1967, pp. 4555.
 [4]
M. C. Pease, "An adaption of the Fast Fourier Transform for parallel processing," J. Assoc. Comput. Mach., v. 15, 1968, pp. 253264.
 [5]
J.
A. Glassman, A generalization of the fast Fourier transform,
IEEE Trans. Computers C19 (1970), 105–116. MR 0253590
(40 #6804)
 [6]
Shmuel
Winograd, On computing the discrete Fourier transform, Proc.
Nat. Acad. Sci. U.S.A. 73 (1976), no. 4,
1005–1006. MR 0415993
(54 #4070)
 [1]
 D. G. Korn & J. J. Lambiotte, Jr., "Computing the Fast Fourier Transform on a vector computer," Math. Comp., v. 33, 1979, pp. 977992. MR 528051 (80k:65108)
 [2]
 J. W. Cooley & J. W. Tukey, "An algorithm for the machine calculation of complex Fourier series," Math. Comp., v. 19, 1965, pp. 297301. MR 0178586 (31:2843)
 [3]
 W. T. Cochran et al., "What is the Fast Fourier Transform?," IEEE Trans. Audio Electroacoust., v. Au15, 1967, pp. 4555.
 [4]
 M. C. Pease, "An adaption of the Fast Fourier Transform for parallel processing," J. Assoc. Comput. Mach., v. 15, 1968, pp. 253264.
 [5]
 J. A. Glassman, "A generalization of the Fast Fourier Transform," IEEE Trans. Comput., v. C19, 1970, pp. 106116. MR 0253590 (40:6804)
 [6]
 S. Winograd, "On computing the discrete Fourier transform," Proc. Nat. Acad. Sci. U.S.A., v. 74, 1976, pp. 10051006. MR 0415993 (54:4070)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
68A10,
42A68
Retrieve articles in all journals
with MSC:
68A10,
42A68
Additional Information
DOI:
http://dx.doi.org/10.1090/S0025571881997830
PII:
S 00255718(81)997830
Article copyright:
© Copyright 1981
American Mathematical Society
