Symmetric FFTs
HTML articles powered by AMS MathViewer
- by Paul N. Swarztrauber PDF
- Math. Comp. 47 (1986), 323-346 Request permission
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
-
G. D. Bergland, "A fast Fourier transform for real-valued series," Comm. ACM, v. 11, 1968, pp. 703-710.
E. O. Brigham, The Fast Fourier Transform, Prentice-Hall, Englewood Cliffs, N. J., 1974.
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.
- Jean Dollimore, Some algorithms for use with the fast Fourier transform, J. Inst. Math. Appl. 12 (1973), 115–117. MR 373238 B. Fornberg, "A vector implementation of the fast Fourier transform," Math. Comp., v. 36, 1981, pp. 189-191.
- R. W. Hockney, A fast direct solution of Poisson’s equation using Fourier analysis, J. Assoc. Comput. Mach. 12 (1965), 95–113. MR 213048, DOI 10.1145/321250.321259
- 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 438732, DOI 10.1137/1019071
- Garry Rodrigue (ed.), Parallel computations, Computational Techniques, vol. 1, Academic Press, Inc., Orlando, FL, 1982. MR 759548
- 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 P. N. Swarztrauber, "FFT algorithms for vector computers," Parallel Computing, v. 1, 1984, pp. 45-63.
- 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
- Clive Temperton, Fast mixed-radix real Fourier transforms, J. Comput. Phys. 52 (1983), no. 2, 340–350. MR 725599, DOI 10.1016/0021-9991(83)90034-7
Additional Information
- © Copyright 1986 American Mathematical Society
- Journal: Math. Comp. 47 (1986), 323-346
- MSC: Primary 65T05
- DOI: https://doi.org/10.1090/S0025-5718-1986-0842139-3
- MathSciNet review: 842139