Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: FFTW 3.3.8: Multi-Dimensional DFTs of Real Data Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82:
Chris@82:

Chris@82: Next: , Previous: , Up: Tutorial   [Contents][Index]

Chris@82:
Chris@82:
Chris@82: Chris@82:

2.4 Multi-Dimensional DFTs of Real Data

Chris@82: Chris@82:

Multi-dimensional DFTs of real data use the following planner routines: Chris@82:

Chris@82:
Chris@82:
fftw_plan fftw_plan_dft_r2c_2d(int n0, int n1,
Chris@82:                                double *in, fftw_complex *out,
Chris@82:                                unsigned flags);
Chris@82: fftw_plan fftw_plan_dft_r2c_3d(int n0, int n1, int n2,
Chris@82:                                double *in, fftw_complex *out,
Chris@82:                                unsigned flags);
Chris@82: fftw_plan fftw_plan_dft_r2c(int rank, const int *n,
Chris@82:                             double *in, fftw_complex *out,
Chris@82:                             unsigned flags);
Chris@82: 
Chris@82: Chris@82: Chris@82: Chris@82: Chris@82:

as well as the corresponding c2r routines with the input/output Chris@82: types swapped. These routines work similarly to their complex Chris@82: analogues, except for the fact that here the complex output array is cut Chris@82: roughly in half and the real array requires padding for in-place Chris@82: transforms (as in 1d, above). Chris@82:

Chris@82:

As before, n is the logical size of the array, and the Chris@82: consequences of this on the the format of the complex arrays deserve Chris@82: careful attention. Chris@82: Chris@82: Suppose that the real data has dimensions n0 × n1 × n2 × … × nd-1 Chris@82: (in row-major order). Chris@82: Then, after an r2c transform, the output is an n0 × n1 × n2 × … × (nd-1/2 + 1) Chris@82: array of Chris@82: fftw_complex values in row-major order, corresponding to slightly Chris@82: over half of the output of the corresponding complex DFT. (The division Chris@82: is rounded down.) The ordering of the data is otherwise exactly the Chris@82: same as in the complex-DFT case. Chris@82:

Chris@82:

For out-of-place transforms, this is the end of the story: the real Chris@82: data is stored as a row-major array of size n0 × n1 × n2 × … × nd-1 Chris@82: and the complex Chris@82: data is stored as a row-major array of size n0 × n1 × n2 × … × (nd-1/2 + 1) Chris@82: . Chris@82:

Chris@82:

For in-place transforms, however, extra padding of the real-data array Chris@82: is necessary because the complex array is larger than the real array, Chris@82: and the two arrays share the same memory locations. Thus, for Chris@82: in-place transforms, the final dimension of the real-data array must Chris@82: be padded with extra values to accommodate the size of the complex Chris@82: data—two values if the last dimension is even and one if it is odd. Chris@82: Chris@82: That is, the last dimension of the real data must physically contain Chris@82: 2 * (nd-1/2+1) Chris@82: double values (exactly enough to hold the complex data). Chris@82: This physical array size does not, however, change the logical Chris@82: array size—only Chris@82: nd-1 Chris@82: values are actually stored in the last dimension, and Chris@82: nd-1 Chris@82: is the last dimension passed to the plan-creation routine. Chris@82:

Chris@82:

For example, consider the transform of a two-dimensional real array of Chris@82: size n0 by n1. The output of the r2c transform is a Chris@82: two-dimensional complex array of size n0 by n1/2+1, where Chris@82: the y dimension has been cut nearly in half because of Chris@82: redundancies in the output. Because fftw_complex is twice the Chris@82: size of double, the output array is slightly bigger than the Chris@82: input array. Thus, if we want to compute the transform in place, we Chris@82: must pad the input array so that it is of size n0 by Chris@82: 2*(n1/2+1). If n1 is even, then there are two padding Chris@82: elements at the end of each row (which need not be initialized, as they Chris@82: are only used for output). Chris@82:

Chris@82:

The following illustration depicts the input and output arrays just Chris@82: described, for both the out-of-place and in-place transforms (with the Chris@82: arrows indicating consecutive memory locations): Chris@82: rfftwnd-for-html Chris@82:

Chris@82:

These transforms are unnormalized, so an r2c followed by a c2r Chris@82: transform (or vice versa) will result in the original data scaled by Chris@82: the number of real data elements—that is, the product of the Chris@82: (logical) dimensions of the real data. Chris@82: Chris@82:

Chris@82: Chris@82:

(Because the last dimension is treated specially, if it is equal to Chris@82: 1 the transform is not equivalent to a lower-dimensional Chris@82: r2c/c2r transform. In that case, the last complex dimension also has Chris@82: size 1 (=1/2+1), and no advantage is gained over the Chris@82: complex transforms.) Chris@82:

Chris@82:
Chris@82:
Chris@82:

Chris@82: Next: , Previous: , Up: Tutorial   [Contents][Index]

Chris@82:
Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: