cannam@167: @node Introduction, Tutorial, Top, Top cannam@167: @chapter Introduction cannam@167: This manual documents version @value{VERSION} of FFTW, the cannam@167: @emph{Fastest Fourier Transform in the West}. FFTW is a comprehensive cannam@167: collection of fast C routines for computing the discrete Fourier cannam@167: transform (DFT) and various special cases thereof. cannam@167: @cindex discrete Fourier transform cannam@167: @cindex DFT cannam@167: @itemize @bullet cannam@167: @item FFTW computes the DFT of complex data, real data, even- cannam@167: or odd-symmetric real data (these symmetric transforms are usually cannam@167: known as the discrete cosine or sine transform, respectively), and the cannam@167: discrete Hartley transform (DHT) of real data. cannam@167: cannam@167: @item The input data can have arbitrary length. cannam@167: FFTW employs @Onlogn{} algorithms for all lengths, including cannam@167: prime numbers. cannam@167: cannam@167: @item FFTW supports arbitrary multi-dimensional data. cannam@167: cannam@167: @item FFTW supports the SSE, SSE2, AVX, AVX2, AVX512, KCVI, Altivec, VSX, and cannam@167: NEON vector instruction sets. cannam@167: cannam@167: @item FFTW includes parallel (multi-threaded) transforms cannam@167: for shared-memory systems. cannam@167: @item Starting with version 3.3, FFTW includes distributed-memory parallel cannam@167: transforms using MPI. cannam@167: @end itemize cannam@167: cannam@167: We assume herein that you are familiar with the properties and uses of cannam@167: the DFT that are relevant to your application. Otherwise, see cannam@167: e.g. @cite{The Fast Fourier Transform and Its Applications} by E. O. Brigham cannam@167: (Prentice-Hall, Englewood Cliffs, NJ, 1988). cannam@167: @uref{http://www.fftw.org, Our web page} also has links to FFT-related cannam@167: information online. cannam@167: @cindex FFTW cannam@167: cannam@167: @c TODO: revise. We don't need to brag any longer cannam@167: @c cannam@167: @c FFTW is usually faster (and sometimes much faster) than all other cannam@167: @c freely-available Fourier transform programs found on the Net. It is cannam@167: @c competitive with (and often faster than) the FFT codes in Sun's cannam@167: @c Performance Library, IBM's ESSL library, HP's CXML library, and cannam@167: @c Intel's MKL library, which are targeted at specific machines. cannam@167: @c Moreover, FFTW's performance is @emph{portable}. Indeed, FFTW is cannam@167: @c unique in that it automatically adapts itself to your machine, your cannam@167: @c cache, the size of your memory, your number of registers, and all the cannam@167: @c other factors that normally make it impossible to optimize a program cannam@167: @c for more than one machine. An extensive comparison of FFTW's cannam@167: @c performance with that of other Fourier transform codes has been made, cannam@167: @c and the results are available on the Web at cannam@167: @c @uref{http://fftw.org/benchfft, the benchFFT home page}. cannam@167: @c @cindex benchmark cannam@167: @c @fpindex benchfft cannam@167: cannam@167: In order to use FFTW effectively, you need to learn one basic concept cannam@167: of FFTW's internal structure: FFTW does not use a fixed algorithm for cannam@167: computing the transform, but instead it adapts the DFT algorithm to cannam@167: details of the underlying hardware in order to maximize performance. cannam@167: Hence, the computation of the transform is split into two phases. cannam@167: First, FFTW's @dfn{planner} ``learns'' the fastest way to compute the cannam@167: transform on your machine. The planner cannam@167: @cindex planner cannam@167: produces a data structure called a @dfn{plan} that contains this cannam@167: @cindex plan cannam@167: information. Subsequently, the plan is @dfn{executed} cannam@167: @cindex execute cannam@167: to transform the array of input data as dictated by the plan. The cannam@167: plan can be reused as many times as needed. In typical cannam@167: high-performance applications, many transforms of the same size are cannam@167: computed and, consequently, a relatively expensive initialization of cannam@167: this sort is acceptable. On the other hand, if you need a single cannam@167: transform of a given size, the one-time cost of the planner becomes cannam@167: significant. For this case, FFTW provides fast planners based on cannam@167: heuristics or on previously computed plans. cannam@167: cannam@167: FFTW supports transforms of data with arbitrary length, rank, cannam@167: multiplicity, and a general memory layout. In simple cases, however, cannam@167: this generality may be unnecessary and confusing. Consequently, we cannam@167: organized the interface to FFTW into three levels of increasing cannam@167: generality. cannam@167: @itemize @bullet cannam@167: @item The @dfn{basic interface} computes a single cannam@167: transform of contiguous data. cannam@167: @item The @dfn{advanced interface} computes transforms cannam@167: of multiple or strided arrays. cannam@167: @item The @dfn{guru interface} supports the most general data cannam@167: layouts, multiplicities, and strides. cannam@167: @end itemize cannam@167: We expect that most users will be best served by the basic interface, cannam@167: whereas the guru interface requires careful attention to the cannam@167: documentation to avoid problems. cannam@167: @cindex basic interface cannam@167: @cindex advanced interface cannam@167: @cindex guru interface cannam@167: cannam@167: cannam@167: Besides the automatic performance adaptation performed by the planner, cannam@167: it is also possible for advanced users to customize FFTW manually. For cannam@167: example, if code space is a concern, we provide a tool that links only cannam@167: the subset of FFTW needed by your application. Conversely, you may need cannam@167: to extend FFTW because the standard distribution is not sufficient for cannam@167: your needs. For example, the standard FFTW distribution works most cannam@167: efficiently for arrays whose size can be factored into small primes cannam@167: (@math{2}, @math{3}, @math{5}, and @math{7}), and otherwise it uses a cannam@167: slower general-purpose routine. If you need efficient transforms of cannam@167: other sizes, you can use FFTW's code generator, which produces fast C cannam@167: programs (``codelets'') for any particular array size you may care cannam@167: about. cannam@167: @cindex code generator cannam@167: @cindex codelet cannam@167: For example, if you need transforms of size cannam@167: @ifinfo cannam@167: @math{513 = 19 x 3^3}, cannam@167: @end ifinfo cannam@167: @tex cannam@167: $513 = 19 \cdot 3^3$, cannam@167: @end tex cannam@167: @html cannam@167: 513 = 19*33, cannam@167: @end html cannam@167: you can customize FFTW to support the factor @math{19} efficiently. cannam@167: cannam@167: For more information regarding FFTW, see the paper, ``The Design and cannam@167: Implementation of FFTW3,'' by M. Frigo and S. G. Johnson, which was an cannam@167: invited paper in @cite{Proc. IEEE} @b{93} (2), p. 216 (2005). The cannam@167: code generator is described in the paper ``A fast Fourier transform cannam@167: compiler'', cannam@167: @cindex compiler cannam@167: by M. Frigo, in the @cite{Proceedings of the 1999 ACM SIGPLAN Conference cannam@167: on Programming Language Design and Implementation (PLDI), Atlanta, cannam@167: Georgia, May 1999}. These papers, along with the latest version of cannam@167: FFTW, the FAQ, benchmarks, and other links, are available at cannam@167: @uref{http://www.fftw.org, the FFTW home page}. cannam@167: cannam@167: The current version of FFTW incorporates many good ideas from the past cannam@167: thirty years of FFT literature. In one way or another, FFTW uses the cannam@167: Cooley-Tukey algorithm, the prime factor algorithm, Rader's algorithm cannam@167: for prime sizes, and a split-radix algorithm (with a cannam@167: ``conjugate-pair'' variation pointed out to us by Dan Bernstein). cannam@167: FFTW's code generator also produces new algorithms that we do not cannam@167: completely understand. cannam@167: @cindex algorithm cannam@167: The reader is referred to the cited papers for the appropriate cannam@167: references. cannam@167: cannam@167: The rest of this manual is organized as follows. We first discuss the cannam@167: sequential (single-processor) implementation. We start by describing cannam@167: the basic interface/features of FFTW in @ref{Tutorial}. cannam@167: Next, @ref{Other Important Topics} discusses data alignment cannam@167: (@pxref{SIMD alignment and fftw_malloc}), cannam@167: the storage scheme of multi-dimensional arrays cannam@167: (@pxref{Multi-dimensional Array Format}), and FFTW's mechanism for cannam@167: storing plans on disk (@pxref{Words of Wisdom-Saving Plans}). Next, cannam@167: @ref{FFTW Reference} provides comprehensive documentation of all cannam@167: FFTW's features. Parallel transforms are discussed in their own cannam@167: chapters: @ref{Multi-threaded FFTW} and @ref{Distributed-memory FFTW cannam@167: with MPI}. Fortran programmers can also use FFTW, as described in cannam@167: @ref{Calling FFTW from Legacy Fortran} and @ref{Calling FFTW from cannam@167: Modern Fortran}. @ref{Installation and Customization} explains how to cannam@167: install FFTW in your computer system and how to adapt FFTW to your cannam@167: needs. License and copyright information is given in @ref{License and cannam@167: Copyright}. Finally, we thank all the people who helped us in cannam@167: @ref{Acknowledgments}. cannam@167: