Chris@19:
Chris@19: The innovation (if it can be so called) in FFTW consists in having a
Chris@19: variety of composable solvers, representing different FFT algorithms and implementation strategies, whose combination into a
Chris@19: particular plan for a given size can be determined at runtime according to the characteristics of your machine/compiler.
Chris@19: This peculiar software architecture allows FFTW to adapt itself to
Chris@19: almost any machine.
Chris@19:
Chris@19: For more details (albeit somewhat outdated), see the paper "FFTW:
Chris@19: An Adaptive Software Architecture for the FFT", by M. Frigo and
Chris@19: S. G. Johnson, Proc. ICASSP 3, 1381 (1998), also available at the FFTW web page.
Chris@19:
Chris@19:
Chris@19: This is a complex question, and there is no simple answer. In fact,
Chris@19: the authors do not fully know the answer, either. In addition to many
Chris@19: small performance hacks throughout FFTW, there are three general
Chris@19: reasons for FFTW's speed.
Chris@19:
Chris@19:
FFTW uses a variety of FFT algorithms and implementation styles
Chris@19: that can be arbitrarily composed to adapt itself to
Chris@19: a machine. See Q4.1 `How does FFTW work?'.
Chris@19:
FFTW uses a code generator to produce highly-optimized
Chris@19: routines for computing small transforms.
Chris@19:
Chris@19:
FFTW uses explicit divide-and-conquer to take advantage
Chris@19: of the memory hierarchy.
Chris@19:
Chris@19: For more details (albeit somewhat outdated), see the paper "FFTW:
Chris@19: An Adaptive Software Architecture for the FFT", by M. Frigo and
Chris@19: S. G. Johnson, Proc. ICASSP 3, 1381 (1998), available along with other references at
Chris@19: the FFTW web page.
Chris@19: Next: Known bugs.
Chris@19: Back: Using FFTW.
Chris@19: Return to contents.