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