In-place self-sorting fast Fourier transform algorithm with local memory references (Q1299629)

To take advantage of modern computer architectures (cache memory, virtual memory, distributed memory parallel computers), locality of references should be one of the programming goals. The memory references of the conventional fast Fourier transform (FFT) algorithm are extremely nonlocal, and for very large problem size, alternative approaches, such as \textit{R. C. Singleton's} algorithm [Commun. ACM 10, 647-654 (1967; Zbl 0149.37301)], are better suited. Singleton's method achieves locality of reference at the cost of being not in-place. The author presents a new in-plane, in-order FFT algorithm with local memory references. For large problem sizes, the new algorithm is about three times faster than the conventional algorithm.