fftw3: Multi-dimensional Transforms
4.8.6 Multi-dimensional Transforms
----------------------------------
The multi-dimensional transforms of FFTW, in general, compute simply the
separable product of the given 1d transform along each dimension of the
array. Since each of these transforms is unnormalized, computing the
forward followed by the backward/inverse multi-dimensional transform
will result in the original array scaled by the product of the
normalization factors for each dimension (e.g. the product of the
dimension sizes, for a multi-dimensional DFT).
The definition of FFTW's multi-dimensional DFT of real data (r2c)
deserves special attention. In this case, we logically compute the full
multi-dimensional DFT of the input data; since the input data are purely
real, the output data have the Hermitian symmetry and therefore only one
non-redundant half need be stored. More specifically, for an n[0] x
n[1] x n[2] x ... x n[d-1] multi-dimensional real-input DFT, the full
(logical) complex output array Y[k[0], k[1], ..., k[d-1]] has the
symmetry: Y[k[0], k[1], ..., k[d-1]] = Y[n[0] - k[0], n[1] - k[1], ...,
n[d-1] - k[d-1]]* (where each dimension is periodic). Because of this
symmetry, we only store the k[d-1] = 0...n[d-1]/2 elements of the _last_
dimension (division by 2 is rounded down). (We could instead have cut
any other dimension in half, but the last dimension proved
computationally convenient.) This results in the peculiar array format
described in more detail by 
Real-data DFT Array Format.
The multi-dimensional c2r transform is simply the unnormalized
inverse of the r2c transform. i.e. it is the same as FFTW's complex
backward multi-dimensional DFT, operating on a Hermitian input array in
the peculiar format mentioned above and outputting a real array (since
the DFT output is purely real).
We should remind the user that the separable product of 1d transforms
along each dimension, as computed by FFTW, is not always the same thing
as the usual multi-dimensional transform. A multi-dimensional 'R2HC'
(or 'HC2R') transform is not identical to the multi-dimensional DFT,
requiring some post-processing to combine the requisite real and
imaginary parts, as was described in The Halfcomplex-format DFT.
Likewise, FFTW's multidimensional 'FFTW_DHT' r2r transform is not the
same thing as the logical multi-dimensional discrete Hartley transform
defined in the literature, as discussed in The Discrete Hartley
Transform.
Info Catalog
fftw3: 1d Discrete Hartley Transforms (DHTs)
fftw3: What FFTW Really Computes