Computing the fast Fourier transform on a vector computer
HTML articles powered by AMS MathViewer
- by David G. Korn and Jules J. Lambiotte PDF
- Math. Comp. 33 (1979), 977-992 Request permission
Abstract:
Two algorithms are presented for performing a Fast Fourier Transform on a vector computer and are compared on the Control Data Corporation STAR-100. 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.References
- 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 M. C. PEASE, "An adaptation of the fast Fourier transform for parallel processing," J. Assoc. Comput. Mach., v. 15, 1968, pp. 253-264.
- Jules J. Lambiotte Jr. and Robert G. Voigt, The solution of tridiagonal linear systems on the CDC STAR-100 computer, ACM Trans. Math. Software 1 (1975), no. 4, 308–329. MR 388843, DOI 10.1145/355656.355658 W. T. COCHRAN ET AL., "What is the fast Fourier transform?," IEEE Trans. Audio Electroacoustics, v. Au-15, 1967, pp. 45-55.
- G. D. Bergland, A fast Fourier transform algorithm using base $8$ iterations, Math. Comp. 22 (1968), 275–279. MR 226899, DOI 10.1090/S0025-5718-1968-0226899-X
Additional Information
- © Copyright 1979 American Mathematical Society
- Journal: Math. Comp. 33 (1979), 977-992
- MSC: Primary 65T05; Secondary 68C25
- DOI: https://doi.org/10.1090/S0025-5718-1979-0528051-4
- MathSciNet review: 528051