On computing the discrete Fourier transform
Author:
S. Winograd
Journal:
Math. Comp. 32 (1978), 175199
MSC:
Primary 68A10
MathSciNet review:
0468306
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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.
 [1]
S. WINOGRAD, "Some bilinear forms whose multiplicative complexity depends on the field of constants," to be published in Mathematical Systems Theory, Vol. 10.
 [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]
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.
 [4]
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
(27 #6417)
 [5]
C. M. RADER, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE, v. 5, no. 6, June 1968, pp. 11071108.
 [6]
I.
J. Good, The interaction algorithm and practical Fourier
analysis, J. Roy. Statist. Soc. Ser. B 20 (1958),
361–372. MR 0102888
(21 #1674)
 [1]
 S. WINOGRAD, "Some bilinear forms whose multiplicative complexity depends on the field of constants," to be published in Mathematical Systems Theory, Vol. 10.
 [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]
 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.
 [4]
 A. L. TOOM, "The complexity of a scheme of functional elements simulating the multiplication of integers," Dokl. Akad. Nauk SSSR, v. 150, 1963, pp. 496498 = Soviet Math. Dokl., v. 4, 1963, pp. 714716. MR 0156494 (27:6417)
 [5]
 C. M. RADER, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE, v. 5, no. 6, June 1968, pp. 11071108.
 [6]
 I. J. GOOD, "The interaction of algorithm and practical Fourier series," J. Roy. Statist. Soc. Ser. B, v. 20, 1958, pp. 361372; Addendum, v. 22, 1960, pp. 372375. MR 0102888 (21:1674)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
68A10
Retrieve articles in all journals
with MSC:
68A10
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197804683064
PII:
S 00255718(1978)04683064
Article copyright:
© Copyright 1978
American Mathematical Society
