Chris@19: Chris@19: Chris@19: Complex Multi-Dimensional DFTs - FFTW 3.3.4 Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19: Chris@19:
Chris@19: Chris@19: Chris@19:

Chris@19: Next: , Chris@19: Previous: Complex One-Dimensional DFTs, Chris@19: Up: Tutorial Chris@19:


Chris@19:
Chris@19: Chris@19:

2.2 Complex Multi-Dimensional DFTs

Chris@19: Chris@19:

Multi-dimensional transforms work much the same way as one-dimensional Chris@19: transforms: you allocate arrays of fftw_complex (preferably Chris@19: using fftw_malloc), create an fftw_plan, execute it as Chris@19: many times as you want with fftw_execute(plan), and clean up Chris@19: with fftw_destroy_plan(plan) (and fftw_free). Chris@19: Chris@19:

FFTW provides two routines for creating plans for 2d and 3d transforms, Chris@19: and one routine for creating plans of arbitrary dimensionality. Chris@19: The 2d and 3d routines have the following signature: Chris@19:

     fftw_plan fftw_plan_dft_2d(int n0, int n1,
Chris@19:                                 fftw_complex *in, fftw_complex *out,
Chris@19:                                 int sign, unsigned flags);
Chris@19:      fftw_plan fftw_plan_dft_3d(int n0, int n1, int n2,
Chris@19:                                 fftw_complex *in, fftw_complex *out,
Chris@19:                                 int sign, unsigned flags);
Chris@19: 
Chris@19:

Chris@19: These routines create plans for n0 by n1 two-dimensional Chris@19: (2d) transforms and n0 by n1 by n2 3d transforms, Chris@19: respectively. All of these transforms operate on contiguous arrays in Chris@19: the C-standard row-major order, so that the last dimension has the Chris@19: fastest-varying index in the array. This layout is described further in Chris@19: Multi-dimensional Array Format. Chris@19: Chris@19:

FFTW can also compute transforms of higher dimensionality. In order to Chris@19: avoid confusion between the various meanings of the the word Chris@19: “dimension”, we use the term rank Chris@19: to denote the number of independent indices in an array.1 For Chris@19: example, we say that a 2d transform has rank 2, a 3d transform has Chris@19: rank 3, and so on. You can plan transforms of arbitrary rank by Chris@19: means of the following function: Chris@19: Chris@19:

     fftw_plan fftw_plan_dft(int rank, const int *n,
Chris@19:                              fftw_complex *in, fftw_complex *out,
Chris@19:                              int sign, unsigned flags);
Chris@19: 
Chris@19:

Chris@19: Here, n is a pointer to an array n[rank] denoting an Chris@19: n[0] by n[1] by ... by n[rank-1] transform. Chris@19: Thus, for example, the call Chris@19:

     fftw_plan_dft_2d(n0, n1, in, out, sign, flags);
Chris@19: 
Chris@19:

is equivalent to the following code fragment: Chris@19:

     int n[2];
Chris@19:      n[0] = n0;
Chris@19:      n[1] = n1;
Chris@19:      fftw_plan_dft(2, n, in, out, sign, flags);
Chris@19: 
Chris@19:

fftw_plan_dft is not restricted to 2d and 3d transforms, Chris@19: however, but it can plan transforms of arbitrary rank. Chris@19: Chris@19:

You may have noticed that all the planner routines described so far Chris@19: have overlapping functionality. For example, you can plan a 1d or 2d Chris@19: transform by using fftw_plan_dft with a rank of 1 Chris@19: or 2, or even by calling fftw_plan_dft_3d with n0 Chris@19: and/or n1 equal to 1 (with no loss in efficiency). This Chris@19: pattern continues, and FFTW's planning routines in general form a Chris@19: “partial order,” sequences of Chris@19: interfaces with strictly increasing generality but correspondingly Chris@19: greater complexity. Chris@19: Chris@19:

fftw_plan_dft is the most general complex-DFT routine that we Chris@19: describe in this tutorial, but there are also the advanced and guru interfaces, Chris@19: which allow one to efficiently combine multiple/strided transforms Chris@19: into a single FFTW plan, transform a subset of a larger Chris@19: multi-dimensional array, and/or to handle more general complex-number Chris@19: formats. For more information, see FFTW Reference. Chris@19: Chris@19: Chris@19:

Chris@19:
Chris@19:

Footnotes

[1] The Chris@19: term “rank” is commonly used in the APL, FORTRAN, and Common Lisp Chris@19: traditions, although it is not so common in the C world.

Chris@19: Chris@19:
Chris@19: Chris@19: Chris@19: