A methodology for designing, modifying, and implementing Fourier transform algorithms on various architectures (Q753467)

The aim of this very well structured paper is to present a theoretical and practical method of obtaining all variations of the algorithms of \textit{J. W. Cooley} and \textit{J. W. Tukey} [Math. Comput. 19, 297-301 (1965; Zbl 0127.090)] for computing fast Fourier transforms. Algorithms are described using tensor products and an associated class of permutations. These algorithms can be implemented by translating tensor products and permutations to programming constructs. For a specific architecture an implementation can be matched by selecting the appropriate variant. For each general scheme, practical examples are included. The methodology is exemplified using the CRAY X-MP's architecture.