cannam@167: cannam@167: Next: More DFTs of Real Data, Previous: One-Dimensional DFTs of Real Data, Up: Tutorial [Contents][Index]
cannam@167:Multi-dimensional DFTs of real data use the following planner routines: cannam@167:
cannam@167:fftw_plan fftw_plan_dft_r2c_2d(int n0, int n1, cannam@167: double *in, fftw_complex *out, cannam@167: unsigned flags); cannam@167: fftw_plan fftw_plan_dft_r2c_3d(int n0, int n1, int n2, cannam@167: double *in, fftw_complex *out, cannam@167: unsigned flags); cannam@167: fftw_plan fftw_plan_dft_r2c(int rank, const int *n, cannam@167: double *in, fftw_complex *out, cannam@167: unsigned flags); cannam@167:
as well as the corresponding c2r routines with the input/output
cannam@167: types swapped. These routines work similarly to their complex
cannam@167: analogues, except for the fact that here the complex output array is cut
cannam@167: roughly in half and the real array requires padding for in-place
cannam@167: transforms (as in 1d, above).
cannam@167:
As before, n is the logical size of the array, and the
cannam@167: consequences of this on the the format of the complex arrays deserve
cannam@167: careful attention.
cannam@167:
cannam@167: Suppose that the real data has dimensions n0 × n1 × n2 × … × nd-1
cannam@167: (in row-major order).
cannam@167: Then, after an r2c transform, the output is an n0 × n1 × n2 × … × (nd-1/2 + 1)
cannam@167: array of
cannam@167: fftw_complex values in row-major order, corresponding to slightly
cannam@167: over half of the output of the corresponding complex DFT. (The division
cannam@167: is rounded down.) The ordering of the data is otherwise exactly the
cannam@167: same as in the complex-DFT case.
cannam@167:
For out-of-place transforms, this is the end of the story: the real cannam@167: data is stored as a row-major array of size n0 × n1 × n2 × … × nd-1 cannam@167: and the complex cannam@167: data is stored as a row-major array of size n0 × n1 × n2 × … × (nd-1/2 + 1) cannam@167: . cannam@167:
cannam@167:For in-place transforms, however, extra padding of the real-data array
cannam@167: is necessary because the complex array is larger than the real array,
cannam@167: and the two arrays share the same memory locations. Thus, for
cannam@167: in-place transforms, the final dimension of the real-data array must
cannam@167: be padded with extra values to accommodate the size of the complex
cannam@167: data—two values if the last dimension is even and one if it is odd.
cannam@167:
cannam@167: That is, the last dimension of the real data must physically contain
cannam@167: 2 * (nd-1/2+1)
cannam@167: double values (exactly enough to hold the complex data).
cannam@167: This physical array size does not, however, change the logical
cannam@167: array size—only
cannam@167: nd-1
cannam@167: values are actually stored in the last dimension, and
cannam@167: nd-1
cannam@167: is the last dimension passed to the plan-creation routine.
cannam@167:
For example, consider the transform of a two-dimensional real array of
cannam@167: size n0 by n1. The output of the r2c transform is a
cannam@167: two-dimensional complex array of size n0 by n1/2+1, where
cannam@167: the y dimension has been cut nearly in half because of
cannam@167: redundancies in the output. Because fftw_complex is twice the
cannam@167: size of double, the output array is slightly bigger than the
cannam@167: input array. Thus, if we want to compute the transform in place, we
cannam@167: must pad the input array so that it is of size n0 by
cannam@167: 2*(n1/2+1). If n1 is even, then there are two padding
cannam@167: elements at the end of each row (which need not be initialized, as they
cannam@167: are only used for output).
cannam@167:
The following illustration depicts the input and output arrays just
cannam@167: described, for both the out-of-place and in-place transforms (with the
cannam@167: arrows indicating consecutive memory locations):
cannam@167:
cannam@167:
These transforms are unnormalized, so an r2c followed by a c2r cannam@167: transform (or vice versa) will result in the original data scaled by cannam@167: the number of real data elements—that is, the product of the cannam@167: (logical) dimensions of the real data. cannam@167: cannam@167:
cannam@167: cannam@167:(Because the last dimension is treated specially, if it is equal to
cannam@167: 1 the transform is not equivalent to a lower-dimensional
cannam@167: r2c/c2r transform. In that case, the last complex dimension also has
cannam@167: size 1 (=1/2+1), and no advantage is gained over the
cannam@167: complex transforms.)
cannam@167:
cannam@167: Next: More DFTs of Real Data, Previous: One-Dimensional DFTs of Real Data, Up: Tutorial [Contents][Index]
cannam@167: