d@0: d@0: d@0: Next: Multi-Dimensional DFTs of Real Data, d@0: Previous: Complex Multi-Dimensional DFTs, d@0: Up: Tutorial d@0:
In many practical applications, the input data in[i] are purely
d@0: real numbers, in which case the DFT output satisfies the “Hermitian”
d@0: redundancy: out[i] is the conjugate of out[n-i]. It is
d@0: possible to take advantage of these circumstances in order to achieve
d@0: roughly a factor of two improvement in both speed and memory usage.
d@0:
d@0:
In exchange for these speed and space advantages, the user sacrifices
d@0: some of the simplicity of FFTW's complex transforms. First of all, the
d@0: input and output arrays are of different sizes and types: the
d@0: input is n real numbers, while the output is n/2+1
d@0: complex numbers (the non-redundant outputs); this also requires slight
d@0: “padding” of the input array for
d@0: in-place transforms. Second, the inverse transform (complex to real)
d@0: has the side-effect of destroying its input array, by default.
d@0: Neither of these inconveniences should pose a serious problem for
d@0: users, but it is important to be aware of them.
d@0:
d@0:
The routines to perform real-data transforms are almost the same as
d@0: those for complex transforms: you allocate arrays of double
d@0: and/or fftw_complex (preferably using fftw_malloc),
d@0: create an fftw_plan, execute it as many times as you want with
d@0: fftw_execute(plan), and clean up with
d@0: fftw_destroy_plan(plan) (and fftw_free). The only
d@0: differences are that the input (or output) is of type double
d@0: and there are new routines to create the plan. In one dimension:
d@0:
d@0:
fftw_plan fftw_plan_dft_r2c_1d(int n, double *in, fftw_complex *out, d@0: unsigned flags); d@0: fftw_plan fftw_plan_dft_c2r_1d(int n, fftw_complex *in, double *out, d@0: unsigned flags); d@0:d@0:
d@0: for the real input to complex-Hermitian output (r2c) and
d@0: complex-Hermitian input to real output (c2r) transforms.
d@0: Unlike the complex DFT planner, there is no sign argument.
d@0: Instead, r2c DFTs are always FFTW_FORWARD and c2r DFTs are
d@0: always FFTW_BACKWARD.
d@0: (For single/long-double precision
d@0: fftwf and fftwl, double should be replaced by
d@0: float and long double, respectively.)
d@0:
d@0: Here, n is the “logical” size of the DFT, not necessarily the
d@0: physical size of the array. In particular, the real (double)
d@0: array has n elements, while the complex (fftw_complex)
d@0: array has n/2+1 elements (where the division is rounded down).
d@0: For an in-place transform,
d@0: in and out are aliased to the same array, which must be
d@0: big enough to hold both; so, the real array would actually have
d@0: 2*(n/2+1) elements, where the elements beyond the first n
d@0: are unused padding. The kth element of the complex array is
d@0: exactly the same as the kth element of the corresponding complex
d@0: DFT. All positive n are supported; products of small factors are
d@0: most efficient, but an O(n log n) algorithm is used even for prime
d@0: sizes.
d@0:
d@0:
As noted above, the c2r transform destroys its input array even for
d@0: out-of-place transforms. This can be prevented, if necessary, by
d@0: including FFTW_PRESERVE_INPUT in the flags, with
d@0: unfortunately some sacrifice in performance.
d@0: This flag is also not currently supported for multi-dimensional real
d@0: DFTs (next section).
d@0:
d@0:
Readers familiar with DFTs of real data will recall that the 0th (the
d@0: “DC”) and n/2-th (the “Nyquist” frequency, when n is
d@0: even) elements of the complex output are purely real. Some
d@0: implementations therefore store the Nyquist element where the DC
d@0: imaginary part would go, in order to make the input and output arrays
d@0: the same size. Such packing, however, does not generalize well to
d@0: multi-dimensional transforms, and the space savings are miniscule in
d@0: any case; FFTW does not support it.
d@0:
d@0:
An alternative interface for one-dimensional r2c and c2r DFTs can be d@0: found in the `r2r' interface (see The Halfcomplex-format DFT), with “halfcomplex”-format output that is the same size d@0: (and type) as the input array. d@0: That interface, although it is not very useful for multi-dimensional d@0: transforms, may sometimes yield better performance. d@0: d@0: d@0: d@0: