Computing the fast Fourier transform on a vector computer
Authors:
David G. Korn and Jules J. Lambiotte
Journal:
Math. Comp. 33 (1979), 977992
MSC:
Primary 65T05; Secondary 68C25
MathSciNet review:
528051
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Two algorithms are presented for performing a Fast Fourier Transform on a vector computer and are compared on the Control Data Corporation STAR100. The relative merits of the two algorithms are shown to depend upon whether only a few or many independent transforms are desired. A theorem is proved which shows that a set of independent transforms can be computed by performing a partial transformation on a single vector. The results of this theorem also apply to nonvector machines and have reduced the average time per transform by a factor of two on the CDC 6600 computer.
 [1]
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
 [2]
M. C. PEASE, "An adaptation of the fast Fourier transform for parallel processing," J. Assoc. Comput. Mach., v. 15, 1968, pp. 253264.
 [3]
Jules
J. Lambiotte Jr. and Robert
G. Voigt, The solution of tridiagonal linear systems on the CDC
STAR100 computer, ACM Trans. Math. Software 1
(1975), no. 4, 308–329. MR 0388843
(52 #9677)
 [4]
W. T. COCHRAN ET AL., "What is the fast Fourier transform?," IEEE Trans. Audio Electroacoustics, v. Au15, 1967, pp. 4555.
 [5]
G.
D. Bergland, A fast Fourier transform algorithm
using base 8 iterations, Math. Comp. 22 (1968), 275–279.
MR
0226899 (37 #2485), http://dx.doi.org/10.1090/S0025571819680226899X
 [1]
 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)
 [2]
 M. C. PEASE, "An adaptation of the fast Fourier transform for parallel processing," J. Assoc. Comput. Mach., v. 15, 1968, pp. 253264.
 [3]
 JULES J. LAMBIOTTE, JR. & ROBERT G. VOIGT, "The solution of tridiagonal linear systems on the CDC STAR100 computer," ACM Trans. Math. Software, v. 1, 1975, pp. 308329. MR 0388843 (52:9677)
 [4]
 W. T. COCHRAN ET AL., "What is the fast Fourier transform?," IEEE Trans. Audio Electroacoustics, v. Au15, 1967, pp. 4555.
 [5]
 G. D. BERGLAND, "A fast Fourier transform using base 8 iterations," Math. Comp., v. 22, 1968, pp. 275279. MR 0226899 (37:2485)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65T05,
68C25
Retrieve articles in all journals
with MSC:
65T05,
68C25
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197905280514
PII:
S 00255718(1979)05280514
Keywords:
Fast Fourier Transform,
parallel computation
Article copyright:
© Copyright 1979 American Mathematical Society
