Chris@82: Next: Real-to-Real Transforms, Previous: Real-data DFTs, Up: Basic Interface [Contents][Index]
Chris@82:The output of a DFT of real data (r2c) contains symmetries that, in
Chris@82: principle, make half of the outputs redundant (see What FFTW Really Computes). (Similarly for the input of an inverse c2r transform.) In
Chris@82: practice, it is not possible to entirely realize these savings in an
Chris@82: efficient and understandable format that generalizes to
Chris@82: multi-dimensional transforms. Instead, the output of the r2c
Chris@82: transforms is slightly over half of the output of the
Chris@82: corresponding complex transform. We do not “pack” the data in any
Chris@82: way, but store it as an ordinary array of fftw_complex values.
Chris@82: In fact, this data is simply a subsection of what would be the array in
Chris@82: the corresponding complex transform.
Chris@82:
Specifically, for a real transform of d (= rank)
Chris@82: dimensions n0 × n1 × n2 × … × nd-1
Chris@82: , the complex data is an n0 × n1 × n2 × … × (nd-1/2 + 1)
Chris@82: array of
Chris@82: fftw_complex values in row-major order (with the division rounded
Chris@82: down). That is, we only store the lower half (non-negative
Chris@82: frequencies), plus one element, of the last dimension of the data from
Chris@82: the ordinary complex transform. (We could have instead taken half of
Chris@82: any other dimension, but implementation turns out to be simpler if the
Chris@82: last, contiguous, dimension is used.)
Chris@82:
For an out-of-place transform, the real data is simply an array with Chris@82: physical dimensions n0 × n1 × n2 × … × nd-1 Chris@82: in row-major order. Chris@82:
Chris@82: Chris@82: Chris@82:For an in-place transform, some complications arise since the complex data
Chris@82: is slightly larger than the real data. In this case, the final
Chris@82: dimension of the real data must be padded with extra values to
Chris@82: accommodate the size of the complex data—two extra if the last
Chris@82: dimension is even and one if it is odd. That is, the last dimension of
Chris@82: the real data must physically contain
Chris@82: 2 * (nd-1/2+1)
Chris@82: double values (exactly enough to hold the complex data). This
Chris@82: physical array size does not, however, change the logical array
Chris@82: size—only
Chris@82: nd-1
Chris@82: values are actually stored in the last dimension, and
Chris@82: nd-1
Chris@82: is the last dimension passed to the planner.
Chris@82:
Chris@82: Next: Real-to-Real Transforms, Previous: Real-data DFTs, Up: Basic Interface [Contents][Index]
Chris@82: