On Some Block Algorithms For Fast Fourier Transforms

. Since the publication of the Cooley-Tukey algorithm a variety of related algorithms for fast Fourier transforms have been suggested by Gentleman/Sande, Stockham, Pease, Johnson/Burrus and others. These algorithms differ mainly in the way they store and access their data. From a numerical point of view, they use splitting which is related to a factorization of the complex Fourier transform matrix into two factors. One factor is usually a multiple Fourier transform of slightly smaller order than the original and the other is a scaled and permuted multiple Fourier transform of minimal order. Depending on the relative position of these matrices in the factorization we speak of decimation in time or decimation in frequency. Although these algorithms contain large amounts of parallelism it does not appear in a uniform way and thus these algorithms are often not optimal for vector or parallel processing as they may generate, e.g., bank conflicts or short vector lengths. This is corrected by..