3.2.1 Row-major Format

The multi-dimensional arrays passed to fftw_plan_dft etcetera are expected to be stored as a single contiguous block in row-major order (sometimes called “C order”). Basically, this means that as you step through adjacent memory locations, the first dimension's index varies most slowly and the last dimension's index varies most quickly.

To be more explicit, let us consider an array of rank d whose dimensions are n₀ × n₁ × n₂ × … × n_d-1. Now, we specify a location in the array by a sequence of d (zero-based) indices, one for each dimension: (i₀, i₁, i₂,..., i_d-1). If the array is stored in row-major order, then this element is located at the position i_d-1 + n_d-1 * (i_d-2 + n_d-2 * (... + n₁ * i₀)).

Note that, for the ordinary complex DFT, each element of the array must be of type fftw_complex; i.e. a (real, imaginary) pair of (double-precision) numbers.

In the advanced FFTW interface, the physical dimensions n from which the indices are computed can be different from (larger than) the logical dimensions of the transform to be computed, in order to transform a subset of a larger array. Note also that, in the advanced interface, the expression above is multiplied by a stride to get the actual array index—this is useful in situations where each element of the multi-dimensional array is actually a data structure (or another array), and you just want to transform a single field. In the basic interface, however, the stride is 1.