Fast Fourier transforms: A tutorial review and a state of the art (Q917259)

The authors start with a historical review of the early contributions towards the fast Fourier transform from Gauss to Cooley-Tukey giving credit to these approaches and then describing the developments of the variants of FFT with and without twiddle factors. The next section is devoted to an extremely well written exposition of the divide and conquer approach that is the basis of all fast algorithms considered subsequently. The different variants of implementing the FFT are discussed in much detail and illustrated by appropriate figures for a better understanding. The actual state of the art is outlined, statements are made about eventual improvements and questions of implementation under the aspect of the modern architectures of computers are discussed. Finally, some particular cases of FFT and related transforms as well as multi- dimensional transforms are reported on.