Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Symmetric FFTs

Author: Paul N. Swarztrauber
Journal: Math. Comp. 47 (1986), 323-346
MSC: Primary 65T05
MathSciNet review: 842139
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we examine the FFT of sequences $ {x_n} = {x_{N + n}}$ with period N that satisfy certain symmetric relations. It is known that one can take advantage of these relations in order to reduce the computing time required by the FFT. For example, the time required for the FFT of a real sequence is about half that required for the FFT of a complex sequence. Also, the time required for the FFT of a real even sequence $ {x_n} = {x_{N - n}}$ requires about half that required for a real sequence. We first define a class of five symmetries that are shown to be "closed" in the sense that if $ {x_n}$ has any one of the symmetries, then no additional symmetries are generated in the course of the FFT. Symmetric FFTs are developed that take advantage of these intermediate symmetries. They do not require the traditional pre- and postprocessing associated with symmetric FFTs and, as a consequence, they are somewhat more efficient and general than existing symmetric FFTs.

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

  • [1] G. D. Bergland, "A fast Fourier transform for real-valued series," Comm. ACM, v. 11, 1968, pp. 703-710.
  • [2] E. O. Brigham, The Fast Fourier Transform, Prentice-Hall, Englewood Cliffs, N. J., 1974.
  • [3] J. W. Cooley, P. A. W. Lewis & P. D. Welsh, "The fast Fourier transform algorithm: Programming considerations in the calculation of sine, cosine and Laplace transforms," J. Sound Vibration, v. 12, 1970, pp. 315-337.
  • [4] J. Dollimore, "Some algorithms for use with the fast Fourier transform," J. Inst. Math. Appl., v. 12, 1973, pp. 115-117. MR 0373238 (51:9439)
  • [5] B. Fornberg, "A vector implementation of the fast Fourier transform," Math. Comp., v. 36, 1981, pp. 189-191.
  • [6] R. W. Hockney, "A fast direct solution of Poisson's equation using Fourier analysis," J. Assoc. Comput. Mach., v. 12, 1965, pp. 95-113. MR 0213048 (35:3913)
  • [7] P. N. Swarztrauber, "The methods of cyclic reduction, Fourier analysis and the FACR algorithm for the discrete solution of Poisson's equation on a rectangle," SIAM Rev., v. 19, 1977, pp. 490-501. MR 0438732 (55:11639)
  • [8] P. N. Swarztrauber, "Vectorizing the FFTs," in Parallel Computations (G. Rodrigue, ed.), Academic Press, New York, 1982, pp. 490-501. MR 759548 (86j:65004)
  • [9] P. N. Swarztrauber, "Software for the spectral analysis of scalar and vector functions on the sphere," in Large Scale Scientific Computation (S. V. Parter, ed.), Academic Press, New York, 1984, pp. 271-299. MR 789991 (86k:65015)
  • [10] P. N. Swarztrauber, "FFT algorithms for vector computers," Parallel Computing, v. 1, 1984, pp. 45-63.
  • [11] P. N. Swarztrauber, "Fast Poisson solvers," MAA Studies in Numerical Analysis, Vol. 24 (G. H. Golub, ed.), Mathematical Association of America, 1984, pp. 319-370. MR 925218
  • [12] C. Temperton, "Fast mixed-radix real Fourier transforms," J. Comput. Phys., v. 52, 1983, pp. 340-350. MR 725599 (85c:65162)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65T05

Retrieve articles in all journals with MSC: 65T05

Additional Information

Keywords: FFT, fast Fourier transform, symmetric FFTs
Article copyright: © Copyright 1986 American Mathematical Society

American Mathematical Society