Symmetric FFTs
Author:
Paul N. Swarztrauber
Journal:
Math. Comp. 47 (1986), 323-346
MSC:
Primary 65T05
DOI:
https://doi.org/10.1090/S0025-5718-1986-0842139-3
MathSciNet review:
842139
Full-text PDF
Abstract | References | Similar Articles | Additional Information
Abstract: In this paper, we examine the FFT of sequences 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
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
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.
- [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)
Retrieve articles in Mathematics of Computation with MSC: 65T05
Retrieve articles in all journals with MSC: 65T05
Additional Information
DOI:
https://doi.org/10.1090/S0025-5718-1986-0842139-3
Keywords:
FFT,
fast Fourier transform,
symmetric FFTs
Article copyright:
© Copyright 1986
American Mathematical Society