0.10 Implementing ffts in practice  (Page 4/21)

One ordering distinction is between recursion and iteration. As expressed above, the Cooley-Tukey algorithm could be thought of asdefining a tree of smaller and smaller DFTs, as depicted in [link] ; for example, a textbook radix-2 algorithm would divide size $n$ into two transforms of size $n/2$ , which are divided into four transforms of size $n/4$ , and so on until a base case is reached (in principle, size 1). This might naturally suggest a recursive implementation inwhich the tree is traversed “depth-first” as in [link] (right) and the algorithm of [link] —one size $n/2$ transform is solved completely before processing the other one, and so on. However, most traditionalFFT implementations are non-recursive (with rare exceptions [link] ) and traverse the tree “breadth-first” [link] as in [link] (left)—in the radix-2 example, they would perform $n$ (trivial) size-1 transforms, then $n/2$ combinations into size-2 transforms, then $n/4$ combinations into size-4 transforms, and so on, thus making ${log}_{2}n$ passes over the whole array. In contrast, as we discuss in "Discussion" , FFTW employs an explicitly recursive strategy that encompasses both depth-first and breadth-first styles, favoring the former since it has sometheoretical and practical advantages as discussed in "FFTs and the Memory Hierarchy" .

A second ordering distinction lies in how the digit-reversal is performed. The classic approach is a single, separate digit-reversalpass following or preceding the arithmetic computations; this approach is so common and so deeply embedded into FFT lore that manypractitioners find it difficult to imagine an FFT without an explicit bit-reversal stage. Although this pass requires only $O\left(n\right)$ time [link] , it can still be non-negligible, especially if the data is out-of-cache; moreover, it neglects the possibility that datareordering during the transform may improve memory locality. Perhaps the oldest alternative is the Stockham auto-sort FFT [link] , [link] , which transforms back and forth between two arrays with each butterfly, transposing one digit eachtime, and was popular to improve contiguity of access for vector computers [link] . Alternatively, an explicitly recursive style, as in FFTW, performs the digit-reversal implicitlyat the “leaves” of its computation when operating out-of-place (see section "Discussion" ). A simple example of this style, which computes in-order output using an out-of-place radix-2FFT without explicit bit-reversal, is shown in the algorithm of [link] [corresponding to [link] (right)]. To operate in-placewith $O\left(1\right)$ scratch storage, one can interleave small matrix transpositions with thebutterflies [link] , [link] , [link] , [link] , and a related strategy in FFTW [link] is briefly described by "Discussion" .