FFTW 3.3.8: Complex One-Dimensional DFTs

The basic usage of FFTW to compute a one-dimensional DFT of size Chris@82: N is simple, and it typically looks something like this code: Chris@82:

Chris@82:

#include <fftw3.h>
Chris@82: ...
Chris@82: {
Chris@82:     fftw_complex *in, *out;
Chris@82:     fftw_plan p;
Chris@82:     ...
Chris@82:     in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
Chris@82:     out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
Chris@82:     p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);
Chris@82:     ...
Chris@82:     fftw_execute(p); /* repeat as needed */
Chris@82:     ...
Chris@82:     fftw_destroy_plan(p);
Chris@82:     fftw_free(in); fftw_free(out);
Chris@82: }
Chris@82:

You must link this code with the fftw3 library. On Unix systems, Chris@82: link with -lfftw3 -lm. Chris@82:

The example code first allocates the input and output arrays. You can Chris@82: allocate them in any way that you like, but we recommend using Chris@82: fftw_malloc, which behaves like Chris@82: Chris@82: malloc except that it properly aligns the array when SIMD Chris@82: instructions (such as SSE and Altivec) are available (see SIMD alignment and fftw_malloc). [Alternatively, we provide a convenient wrapper function fftw_alloc_complex(N) which has the same effect.] Chris@82: Chris@82: Chris@82:

The data is an array of type fftw_complex, which is by default a Chris@82: double[2] composed of the real (in[i][0]) and imaginary Chris@82: (in[i][1]) parts of a complex number. Chris@82: Chris@82:

The next step is to create a plan, which is an object Chris@82: Chris@82: that contains all the data that FFTW needs to compute the FFT. Chris@82: This function creates the plan: Chris@82:

Chris@82:

fftw_plan fftw_plan_dft_1d(int n, fftw_complex *in, fftw_complex *out,
Chris@82:                            int sign, unsigned flags);
Chris@82:

The first argument, n, is the size of the transform you are Chris@82: trying to compute. The size n can be any positive integer, but Chris@82: sizes that are products of small factors are transformed most Chris@82: efficiently (although prime sizes still use an O(n log n) Chris@82: algorithm). Chris@82:

The next two arguments are pointers to the input and output arrays of Chris@82: the transform. These pointers can be equal, indicating an Chris@82: in-place transform. Chris@82: Chris@82:

The fourth argument, sign, can be either FFTW_FORWARD Chris@82: (-1) or FFTW_BACKWARD (+1), Chris@82: Chris@82: Chris@82: and indicates the direction of the transform you are interested in; Chris@82: technically, it is the sign of the exponent in the transform. Chris@82:

The flags argument is usually either FFTW_MEASURE or Chris@82: Chris@82: FFTW_ESTIMATE. FFTW_MEASURE instructs FFTW to run Chris@82: Chris@82: and measure the execution time of several FFTs in order to find the Chris@82: best way to compute the transform of size n. This process takes Chris@82: some time (usually a few seconds), depending on your machine and on Chris@82: the size of the transform. FFTW_ESTIMATE, on the contrary, Chris@82: does not run any computation and just builds a Chris@82: Chris@82: reasonable plan that is probably sub-optimal. In short, if your Chris@82: program performs many transforms of the same size and initialization Chris@82: time is not important, use FFTW_MEASURE; otherwise use the Chris@82: estimate. Chris@82:

You must create the plan before initializing the input, because Chris@82: FFTW_MEASURE overwrites the in/out arrays. Chris@82: (Technically, FFTW_ESTIMATE does not touch your arrays, but you Chris@82: should always create plans first just to be sure.) Chris@82:

Once the plan has been created, you can use it as many times as you Chris@82: like for transforms on the specified in/out arrays, Chris@82: computing the actual transforms via fftw_execute(plan): Chris@82:

Chris@82:

void fftw_execute(const fftw_plan plan);
Chris@82:

The DFT results are stored in-order in the array out, with the Chris@82: zero-frequency (DC) component in out[0]. Chris@82: Chris@82: If in != out, the transform is out-of-place and the input Chris@82: array in is not modified. Otherwise, the input array is Chris@82: overwritten with the transform. Chris@82:

If you want to transform a different array of the same size, you Chris@82: can create a new plan with fftw_plan_dft_1d and FFTW Chris@82: automatically reuses the information from the previous plan, if Chris@82: possible. Alternatively, with the “guru” interface you can apply a Chris@82: given plan to a different array, if you are careful. Chris@82: See FFTW Reference. Chris@82:

When you are done with the plan, you deallocate it by calling Chris@82: fftw_destroy_plan(plan): Chris@82:

Chris@82:

void fftw_destroy_plan(fftw_plan plan);
Chris@82:

If you allocate an array with fftw_malloc() you must deallocate Chris@82: it with fftw_free(). Do not use free() or, heaven Chris@82: forbid, delete. Chris@82: Chris@82:

FFTW computes an unnormalized DFT. Thus, computing a forward Chris@82: followed by a backward transform (or vice versa) results in the original Chris@82: array scaled by n. For the definition of the DFT, see What FFTW Really Computes. Chris@82: Chris@82: Chris@82:

If you have a C compiler, such as gcc, that supports the Chris@82: C99 standard, and you #include <complex.h> before Chris@82: <fftw3.h>, then fftw_complex is the native Chris@82: double-precision complex type and you can manipulate it with ordinary Chris@82: arithmetic. Otherwise, FFTW defines its own complex type, which is Chris@82: bit-compatible with the C99 complex type. See Complex numbers. Chris@82: (The C++ <complex> template class may also be usable via a Chris@82: typecast.) Chris@82: Chris@82:

To use single or long-double precision versions of FFTW, replace the Chris@82: fftw_ prefix by fftwf_ or fftwl_ and link with Chris@82: -lfftw3f or -lfftw3l, but use the same Chris@82: <fftw3.h> header file. Chris@82: Chris@82:

Many more flags exist besides FFTW_MEASURE and Chris@82: FFTW_ESTIMATE. For example, use FFTW_PATIENT if you’re Chris@82: willing to wait even longer for a possibly even faster plan (see FFTW Reference). Chris@82: Chris@82: You can also save plans for future use, as described by Words of Wisdom-Saving Plans. Chris@82:

2.1 Complex One-Dimensional DFTs