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]**Jean Dollimore,*Some algorithms for use with the fast Fourier transform*, J. Inst. Math. Appl.**12**(1973), 115–117. MR**0373238****[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.**12**(1965), 95–113. MR**0213048**, https://doi.org/10.1145/321250.321259**[7]**Paul 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.**19**(1977), no. 3, 490–501. MR**0438732**, https://doi.org/10.1137/1019071**[8]**Garry Rodrigue (ed.),*Parallel computations*, Computational Techniques, vol. 1, Academic Press, Inc., Orlando, FL, 1982. MR**759548****[9]**Paul N. Swarztrauber,*Software for the spectral analysis of scalar and vector functions on the sphere*, Large scale scientific computation (Madison, Wis., 1983) Academic Press, Orlando, FL, 1984, pp. 271–299. MR**789991****[10]**P. N. Swarztrauber, "FFT algorithms for vector computers,"*Parallel Computing*, v. 1, 1984, pp. 45-63.**[11]**Paul N. Swarztrauber,*Fast Poisson solvers*, Studies in numerical analysis, MAA Stud. Math., vol. 24, Math. Assoc. America, Washington, DC, 1984, pp. 319–370. MR**925218****[12]**Clive Temperton,*Fast mixed-radix real Fourier transforms*, J. Comput. Phys.**52**(1983), no. 2, 340–350. MR**725599**, https://doi.org/10.1016/0021-9991(83)90034-7

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