Node:Real-data DFT Array Format, Next:Real-to-Real Transforms, Previous:Real-data DFTs, Up:Basic Interface

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_{1} x n_{2} x n_{3} x ... x n_{d}
, the complex data is an n_{1} x n_{2} x n_{3} x ... x (n_{d}/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_{1} x n_{2} x n_{3} x ... x n_{d}
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}/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}
values are actually stored in the last dimension, and
n_{d}
is the last dimension passed to the planner.