0.10 Implementing ffts in practice  (Page 21/21)

There are, in fact, trigonometric recurrences with the same logarithmic error growth as the FFT, but these seem more difficultto implement efficiently; they require that a table of $\Theta (logn)$ values be stored and updated as the recurrence progresses [link] , [link] . Instead, in order to gain at least some of the benefits of a trigonometric recurrence (reducedmemory pressure at the expense of more arithmetic), FFTW includes several ways to compute a much smaller twiddle table, from which thedesired entries can be computed accurately on the fly using a bounded number (usually $<3$ ) of complex multiplications. For example, instead of a twiddle table with $n$ entries ${\omega }_n^k$ , FFTW can use two tables with $\Theta \left(\sqrt{n}\right)$ entries each, so that ${\omega }_n^k$ is computed by multiplying an entry in one table (indexed with the low-order bits of $k$ ) by an entry in the other table (indexed with the high-order bits of $k$ ).

There are a few non-Cooley-Tukey algorithms that are known to have worse error characteristics, such as the “real-factor”algorithm [link] , [link] , but these are rarely used in practice (and are not used at all in FFTW). On the other hand,some commonly used algorithms for type-I and type-IV discrete cosine transforms [link] , [link] , [link] have errors that we observed to grow as $\sqrt{n}$ even for accurate trigonometric constants (although we are not aware of any theoretical error analysisof these algorithms), and thus we were forced to use alternative algorithms [link] .

To measure the accuracy of FFTW, we compare against a slow FFT implemented in arbitrary-precision arithmetic, while to verify thecorrectness we have found the $O(nlogn)$ self-test algorithm of [link] very useful.

Concluding remarks

It is unlikely that many readers of this chapter will ever have to implement their own fast Fourier transform software, except as alearning exercise. The computation of the DFT, much like basic linear algebra or integration of ordinary differential equations, isso central to numerical computing and so well-established that robust, flexible, highly optimized libraries are widely available, for themost part as free/open-source software. And yet there are many other problems for which the algorithms are not so finalized, or for whichalgorithms are published but the implementations are unavailable or of poor quality. Whatever new problems one comes across, thereis a good chance that the chasm between theory and efficient implementation will be just as large as it is for FFTs, unlesscomputers become much simpler in the future. For readers who encounter such a problem, we hope that these lessons from FFTW will beuseful:

• Generality and portability should almost always come first.
• The number of operations, up to a constant factor, is less important than the order of operations.
• Recursive algorithms with large base cases make optimization easier.
• Optimization, like any tedious task, is best automated.
• Code generation reconciles high-level programming with low-level performance.

We should also mention one final lesson that we haven't discussed in this chapter: you can't optimize in a vacuum, or you end upcongratulating yourself for making a slow program slightly faster. We started the FFTW project after downloading a dozen FFTimplementations, benchmarking them on a few machines, and noting how the winners varied between machines and between transform sizes.Throughout FFTW's development, we continued to benefit from repeated benchmarks against the dozens of high-quality FFT programsavailable online, without which we would have thought FFTW was “complete” long ago.

Acknowledgements

SGJ was supported in part by the Materials Research Science and Engineering Center program of the National Science Foundation underaward DMR-9400334; MF was supported in part by the Defense Advanced Research Projects Agency (DARPA) under contract No. NBCH30390004. Weare also grateful to Sidney Burrus for the opportunity to contribute this chapter, and for his continual encouragement—dating back to hisfirst kind words in 1997 for the initial FFT efforts of two graduate students venturing outside their fields.