cannam@95: Next: Tutorial, cannam@95: Previous: Top, cannam@95: Up: Top cannam@95:
This manual documents version 3.3.3 of FFTW, the cannam@95: Fastest Fourier Transform in the West. FFTW is a comprehensive cannam@95: collection of fast C routines for computing the discrete Fourier cannam@95: transform (DFT) and various special cases thereof. cannam@95: cannam@95:
We assume herein that you are familiar with the properties and uses of cannam@95: the DFT that are relevant to your application. Otherwise, see cannam@95: e.g. The Fast Fourier Transform and Its Applications by E. O. Brigham cannam@95: (Prentice-Hall, Englewood Cliffs, NJ, 1988). cannam@95: Our web page also has links to FFT-related cannam@95: information online. cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95: cannam@95:
In order to use FFTW effectively, you need to learn one basic concept cannam@95: of FFTW's internal structure: FFTW does not use a fixed algorithm for cannam@95: computing the transform, but instead it adapts the DFT algorithm to cannam@95: details of the underlying hardware in order to maximize performance. cannam@95: Hence, the computation of the transform is split into two phases. cannam@95: First, FFTW's planner “learns” the fastest way to compute the cannam@95: transform on your machine. The planner cannam@95: produces a data structure called a plan that contains this cannam@95: information. Subsequently, the plan is executed cannam@95: to transform the array of input data as dictated by the plan. The cannam@95: plan can be reused as many times as needed. In typical cannam@95: high-performance applications, many transforms of the same size are cannam@95: computed and, consequently, a relatively expensive initialization of cannam@95: this sort is acceptable. On the other hand, if you need a single cannam@95: transform of a given size, the one-time cost of the planner becomes cannam@95: significant. For this case, FFTW provides fast planners based on cannam@95: heuristics or on previously computed plans. cannam@95: cannam@95:
FFTW supports transforms of data with arbitrary length, rank, cannam@95: multiplicity, and a general memory layout. In simple cases, however, cannam@95: this generality may be unnecessary and confusing. Consequently, we cannam@95: organized the interface to FFTW into three levels of increasing cannam@95: generality. cannam@95:
Besides the automatic performance adaptation performed by the planner, cannam@95: it is also possible for advanced users to customize FFTW manually. For cannam@95: example, if code space is a concern, we provide a tool that links only cannam@95: the subset of FFTW needed by your application. Conversely, you may need cannam@95: to extend FFTW because the standard distribution is not sufficient for cannam@95: your needs. For example, the standard FFTW distribution works most cannam@95: efficiently for arrays whose size can be factored into small primes cannam@95: (2, 3, 5, and 7), and otherwise it uses a cannam@95: slower general-purpose routine. If you need efficient transforms of cannam@95: other sizes, you can use FFTW's code generator, which produces fast C cannam@95: programs (“codelets”) for any particular array size you may care cannam@95: about. cannam@95: For example, if you need transforms of size cannam@95: 513 = 19*33,you can customize FFTW to support the factor 19 efficiently. cannam@95: cannam@95:
For more information regarding FFTW, see the paper, “The Design and cannam@95: Implementation of FFTW3,” by M. Frigo and S. G. Johnson, which was an cannam@95: invited paper in Proc. IEEE 93 (2), p. 216 (2005). The cannam@95: code generator is described in the paper “A fast Fourier transform cannam@95: compiler”, cannam@95: by M. Frigo, in the Proceedings of the 1999 ACM SIGPLAN Conference cannam@95: on Programming Language Design and Implementation (PLDI), Atlanta, cannam@95: Georgia, May 1999. These papers, along with the latest version of cannam@95: FFTW, the FAQ, benchmarks, and other links, are available at cannam@95: the FFTW home page. cannam@95: cannam@95:
The current version of FFTW incorporates many good ideas from the past cannam@95: thirty years of FFT literature. In one way or another, FFTW uses the cannam@95: Cooley-Tukey algorithm, the prime factor algorithm, Rader's algorithm cannam@95: for prime sizes, and a split-radix algorithm (with a cannam@95: “conjugate-pair” variation pointed out to us by Dan Bernstein). cannam@95: FFTW's code generator also produces new algorithms that we do not cannam@95: completely understand. cannam@95: The reader is referred to the cited papers for the appropriate cannam@95: references. cannam@95: cannam@95:
The rest of this manual is organized as follows. We first discuss the cannam@95: sequential (single-processor) implementation. We start by describing cannam@95: the basic interface/features of FFTW in Tutorial. cannam@95: Next, Other Important Topics discusses data alignment cannam@95: (see SIMD alignment and fftw_malloc), cannam@95: the storage scheme of multi-dimensional arrays cannam@95: (see Multi-dimensional Array Format), and FFTW's mechanism for cannam@95: storing plans on disk (see Words of Wisdom-Saving Plans). Next, cannam@95: FFTW Reference provides comprehensive documentation of all cannam@95: FFTW's features. Parallel transforms are discussed in their own cannam@95: chapters: Multi-threaded FFTW and Distributed-memory FFTW with MPI. Fortran programmers can also use FFTW, as described in cannam@95: Calling FFTW from Legacy Fortran and Calling FFTW from Modern Fortran. Installation and Customization explains how to cannam@95: install FFTW in your computer system and how to adapt FFTW to your cannam@95: needs. License and copyright information is given in License and Copyright. Finally, we thank all the people who helped us in cannam@95: Acknowledgments. cannam@95: cannam@95: cannam@95: