4.3.4 Real-data DFT Array Format

The output of a DFT of real data (r2c) contains symmetries that, in principle, make half of the outputs redundant (see What FFTW Really Computes). (Similarly for the input of an inverse c2r transform.) In practice, it is not possible to entirely realize these savings in an efficient and understandable format that generalizes to multi-dimensional transforms. Instead, the output of the r2c transforms is slightly over half of the output of the corresponding complex transform. We do not “pack” the data in any way, but store it as an ordinary array of fftw_complex values. In fact, this data is simply a subsection of what would be the array in the corresponding complex transform.

Specifically, for a real transform of d (= rank) dimensions n₀ × n₁ × n₂ × … × n_d-1, the complex data is an n₀ × n₁ × n₂ × … × (n_d-1/2 + 1) array of fftw_complex values in row-major order (with the division rounded down). That is, we only store the lower half (non-negative frequencies), plus one element, of the last dimension of the data from the ordinary complex transform. (We could have instead taken half of any other dimension, but implementation turns out to be simpler if the last, contiguous, dimension is used.)

For an out-of-place transform, the real data is simply an array with physical dimensions n₀ × n₁ × n₂ × … × n_d-1 in row-major order.

For an in-place transform, some complications arise since the complex data is slightly larger than the real data. In this case, the final dimension of the real data must be padded with extra values to accommodate the size of the complex data—two extra if the last dimension is even and one if it is odd. That is, the last dimension of the real data must physically contain 2 * (n_d-1/2+1)double values (exactly enough to hold the complex data). This physical array size does not, however, change the logical array size—only n_d-1values are actually stored in the last dimension, and n_d-1is the last dimension passed to the planner.