Bluestein's FFT for arbitrary \(N\) on the hypercube (Q1179208): Difference between revisions

Let \(N>1\) be an arbitrary integer, not necessarily a power of 2. The algorithm of \textit{L. I. Bluestein} [A linear filtering approach to the computation of the discrete Fourier transform, 1968 NEREM Record, Boston, MA, Nov. 6-8, 218-219 (1968). Reprinted in: Papers on Digital Signal Processing, ed. A. V. Oppenheim, M.I.T. Press, Cambridge, MA, 171-172 (1969)] for the discrete Fourier transform of length \(N\) (\(DFT(N)\)) consists the following steps: 1. The \(DFT(N)\) is expressed as a Toeplitz matrix-vector-product. 2. This product is imbedded in a cyclic convolution of length \(2^ r \geq 2N-2\). 3. The cyclic convolution is evaluated using \(DFT(2^ r)\). Because of its minimal communication requirements, Bluestein's fast Fourier transformation (\(FFT\)) is realized as an algorithm on hypercube architecture. With \(2^ d\) processors, an ordered Bluestein \(FFT\) requires \(2d\) communication cycles with packet length \(N/2^{d+1}\). For fine-grain computations, Bluestein's \(FFT\) requires \(20\log_ 2N\) computational cycles.