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