A self-sorting in-place fast Fourier transform algorithm suitable for vector and parallel processing (Q1338818): Difference between revisions

The paper presents a unifying framework for fast Fourier transform algorithms which includes most of the known implementations and also a new version, which is especially suitable for vector and parallel processing. Advantages of the new variant are that it is in-place, it is naturally self-sorting and accesses data only with stride one. Moreover, it is efficient: the number of operations is bounded by the operation count for the traditional radix 2 algorithms. It is based on mixed-radix representation of integers and permutations of the ``digits'' in such a representation. The latter can be interpreted in terms of Kronecker products. A special section is devoted to this topic. An FFT algorithm can be described as a matrix multiplication. The algorithms presented here are also discussed in terms of factorizations of these matrices. The paper is quite self-contained with ample referencing to the literature. The algorithms are detailed up to a pseudo code level.