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