Portal de Periódicos da CAPES

A Generalized Prime Factor FFT Algorithm for any $N = 2^p 3^q 5^r $

1992; Society for Industrial and Applied Mathematics; Volume: 13; Issue: 3 Linguagem: Inglês

10.1137/0913039

2168-3417

Clive Temperton,

Numerical Methods and Algorithms

Prime factor fast Fourier transform (FFT) algorithms have two important advantages: they can be simultaneously self-sorting and in-place, and they have a lower operation count than conventional FFT algorithms. The major disadvantage of the prime factor FFT has been that it was only applicable to a limited set of values of the transform length N. This paper presents a generalized prime factor FFT, which is applicable for any $N = 2^p 3^q 5^r $, while maintaining both the self-sorting in-place capability and the lower operation count. Timing experiments on the Cray Y-MP demonstrate the advantages of the new algorithm.