0.10 Implementing ffts in practice

by Steven G. Johnson (Department of Mathematics, Massachusetts Institute of Technology) and Matteo Frigo (Cilk Arts, Inc.)

Introduction

Although there are a wide range of fast Fourier transform (FFT) algorithms, involving a wealth of mathematics from number theory topolynomial algebras, the vast majority of FFT implementations in practice employ some variation on the Cooley-Tukeyalgorithm [link] . The Cooley-Tukey algorithm can be derived in two or three lines of elementary algebra. It can beimplemented almost as easily, especially if only power-of-two sizes are desired; numerous popular textbooks list short FFT subroutinesfor power-of-two sizes, written in the language du jour . The implementation of the Cooley-Tukey algorithm, at least, wouldtherefore seem to be a long-solved problem. In this chapter, however, we will argue that matters are not as straightforward as they mightappear.

For many years, the primary route to improving upon the Cooley-Tukey FFT seemed to be reductions in the count of arithmetic operations,which often dominated the execution time prior to the ubiquity of fast floating-point hardware (at least on non-embedded processors). Therefore, great effort was expended towardsfinding new algorithms with reduced arithmetic counts [link] , from Winograd's method to achieve $\Theta \left(n\right)$ multiplications We employ the standard asymptotic notation of $O$ for asymptotic upper bounds, $\Theta$ for asymptotic tight bounds, and $\Omega$ for asymptotic lower bounds [link] . (at the cost of many more additions) [link] , [link] , [link] , [link] to the split-radix variant on Cooley-Tukey that long achieved the lowestknown total count of additions and multiplications for power-of-two sizes [link] , [link] , [link] , [link] , [link] (but was recently improved upon [link] , [link] ). The question of the minimum possible arithmetic count continues to be of fundamentaltheoretical interest—it is not even known whether better than $\Theta (nlogn)$ complexity is possible, since $\Omega (nlogn)$ lower bounds on the count of additions have only been proven subject to restrictive assumptions about thealgorithms [link] , [link] , [link] . Nevertheless, the difference in the number of arithmetic operations, forpower-of-two sizes $n$ , between the 1965 radix-2 Cooley-Tukey algorithm ( $\sim 5n{log}_{2}n$ [link] ) and the currently lowest-known arithmetic count ( $\sim \frac{34}{9}n{log}_{2}n$ [link] , [link] ) remains only about 25%.