fftw3: Real-data DFT Array Format
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 (
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[0] x
n[1] x n[2] x ... x n[d-1] , the complex data is an n[0] x n[1] x n[2]
x ... x (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[0] x n[1] x n[2] x ... x 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-1] values
are actually stored in the last dimension, and n[d-1] is the last
dimension passed to the planner.
Info Catalog
fftw3: Real-data DFTs
fftw3: Basic Interface
fftw3: Real-to-Real Transforms