Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

On computing the discrete Fourier transform


Author: S. Winograd
Journal: Math. Comp. 32 (1978), 175-199
MSC: Primary 68A10
DOI: https://doi.org/10.1090/S0025-5718-1978-0468306-4
MathSciNet review: 0468306
Full-text PDF

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.


References [Enhancements On Off] (What's this?)

  • [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. 297-301. 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. 496-498 = Soviet Math. Dokl., v. 4, 1963, pp. 714-716. 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. 1107-1108.
  • [6] I. J. GOOD, "The interaction of algorithm and practical Fourier series," J. Roy. Statist. Soc. Ser. B, v. 20, 1958, pp. 361-372; Addendum, v. 22, 1960, pp. 372-375. 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: https://doi.org/10.1090/S0025-5718-1978-0468306-4
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society