Authors: H. Munthe-Kaas

Journal: SIAM J. Sci Comput., Vol 14, No. 2, pp. 349-367, 1993.

Abstract: Fast Fourier transform (FFT) algorithms for single instruction multiple data (SIMD) machines are developed which simultaneously solve any combination of FFTs of different sizes and even different spatial dimensionalities. The only restrictions are that all the periods must be powers of two and that the initial data must satisfy some alignment requirements with the address space in the computer. The degree of parallelism is equal to the sum of the sizes of all the subproblems and the (parallel) solution time is proportional to $\log _2 (m)$, where $m$ is the number of points in the largest subsystem. It is shown that the task of unscrambling the data can be both executed and scheduled efficiently in parallel. Finally, implementations on the MasPar computer are described. The codes can be quickly and easily employed in solving complicated problems, and the interface for the routines may therefore be interesting for sequential FFT codes as well.

Hindsight notes: My software package SPFFT was definitely the fastest FFT library for the MASPAR computer. It was employed in several industrial projects, both weather forecasting (HIRLAM) and SAR radar imaging.