d@0: d@0: d@0: Introduction - FFTW 3.2.1 d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0:
d@0:

d@0: d@0: Next: , d@0: Previous: Top, d@0: Up: Top d@0:


d@0:
d@0: d@0:

1 Introduction

d@0: d@0:

This manual documents version 3.2.1 of FFTW, the d@0: Fastest Fourier Transform in the West. FFTW is a comprehensive d@0: collection of fast C routines for computing the discrete Fourier d@0: transform (DFT) and various special cases thereof. d@0: d@0:

d@0: d@0:

We assume herein that you are familiar with the properties and uses of d@0: the DFT that are relevant to your application. Otherwise, see d@0: e.g. The Fast Fourier Transform and Its Applications by E. O. Brigham d@0: (Prentice-Hall, Englewood Cliffs, NJ, 1988). d@0: Our web page also has links to FFT-related d@0: information online. d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0: d@0:

In order to use FFTW effectively, you need to learn one basic concept d@0: of FFTW's internal structure: FFTW does not use a fixed algorithm for d@0: computing the transform, but instead it adapts the DFT algorithm to d@0: details of the underlying hardware in order to maximize performance. d@0: Hence, the computation of the transform is split into two phases. d@0: First, FFTW's planner “learns” the fastest way to compute the d@0: transform on your machine. The planner d@0: produces a data structure called a plan that contains this d@0: information. Subsequently, the plan is executed d@0: to transform the array of input data as dictated by the plan. The d@0: plan can be reused as many times as needed. In typical d@0: high-performance applications, many transforms of the same size are d@0: computed and, consequently, a relatively expensive initialization of d@0: this sort is acceptable. On the other hand, if you need a single d@0: transform of a given size, the one-time cost of the planner becomes d@0: significant. For this case, FFTW provides fast planners based on d@0: heuristics or on previously computed plans. d@0: d@0:

FFTW supports transforms of data with arbitrary length, rank, d@0: multiplicity, and a general memory layout. In simple cases, however, d@0: this generality may be unnecessary and confusing. Consequently, we d@0: organized the interface to FFTW into three levels of increasing d@0: generality. d@0:

d@0: We expect that most users will be best served by the basic interface, d@0: whereas the guru interface requires careful attention to the d@0: documentation to avoid problems. d@0: d@0: Besides the automatic performance adaptation performed by the planner, d@0: it is also possible for advanced users to customize FFTW manually. For d@0: example, if code space is a concern, we provide a tool that links only d@0: the subset of FFTW needed by your application. Conversely, you may need d@0: to extend FFTW because the standard distribution is not sufficient for d@0: your needs. For example, the standard FFTW distribution works most d@0: efficiently for arrays whose size can be factored into small primes d@0: (2, 3, 5, and 7), and otherwise it uses a d@0: slower general-purpose routine. If you need efficient transforms of d@0: other sizes, you can use FFTW's code generator, which produces fast C d@0: programs (“codelets”) for any particular array size you may care d@0: about. d@0: For example, if you need transforms of size d@0: 513 = 19*33,you can customize FFTW to support the factor 19 efficiently. d@0: d@0:

For more information regarding FFTW, see the paper, “The Design and d@0: Implementation of FFTW3,” by M. Frigo and S. G. Johnson, which was an d@0: invited paper in Proc. IEEE 93 (2), p. 216 (2005). The d@0: code generator is described in the paper “A fast Fourier transform d@0: compiler”, d@0: by M. Frigo, in the Proceedings of the 1999 ACM SIGPLAN Conference d@0: on Programming Language Design and Implementation (PLDI), Atlanta, d@0: Georgia, May 1999. These papers, along with the latest version of d@0: FFTW, the FAQ, benchmarks, and other links, are available at d@0: the FFTW home page. d@0: d@0:

The current version of FFTW incorporates many good ideas from the past d@0: thirty years of FFT literature. In one way or another, FFTW uses the d@0: Cooley-Tukey algorithm, the prime factor algorithm, Rader's algorithm d@0: for prime sizes, and a split-radix algorithm (with a variation due to d@0: Dan Bernstein). FFTW's code generator also produces new algorithms d@0: that we do not completely understand. d@0: The reader is referred to the cited papers for the appropriate d@0: references. d@0: d@0:

The rest of this manual is organized as follows. We first discuss the d@0: sequential (single-processor) implementation. We start by describing d@0: the basic interface/features of FFTW in Tutorial. The following d@0: chapter discusses Other Important Topics, including Data Alignment, the storage scheme of multi-dimensional arrays d@0: (see Multi-dimensional Array Format), and FFTW's mechanism for d@0: storing plans on disk (see Words of Wisdom-Saving Plans). Next, d@0: FFTW Reference provides comprehensive documentation of all d@0: FFTW's features. Parallel transforms are discussed in their own d@0: chapters: Multi-threaded FFTW. Fortran programmers can also use d@0: FFTW, as described in Calling FFTW from Fortran. d@0: Installation and Customization explains how to install FFTW in d@0: your computer system and how to adapt FFTW to your needs. License and d@0: copyright information is given in License and Copyright. d@0: Finally, we thank all the people who helped us in d@0: Acknowledgments. d@0: d@0: d@0: d@0: