fftw3: The Halfcomplex-format DFT
2.5.1 The Halfcomplex-format DFT
--------------------------------
One-Dimensional DFTs of Real Data::) but with "halfcomplex" format
output, and may sometimes be faster and/or more convenient than the
latter. The inverse "hc2r" transform is of kind 'FFTW_HC2R'. This
consists of the non-redundant half of the complex output for a 1d
real-input DFT of size 'n', stored as a sequence of 'n' real numbers
('double') in the format:
r0, r1, r2, r(n/2), i((n+1)/2-1), ..., i2, i1
Here, rk is the real part of the kth output, and ik is the imaginary
part. (Division by 2 is rounded down.) For a halfcomplex array
'hc[n]', the kth component thus has its real part in 'hc[k]' and its
imaginary part in 'hc[n-k]', with the exception of 'k' '==' '0' or 'n/2'
(the latter only if 'n' is even)--in these two cases, the imaginary part
is zero due to symmetries of the real-input DFT, and is not stored.
Thus, the r2hc transform of 'n' real values is a halfcomplex array of
length 'n', and vice versa for hc2r.
Aside from the differing format, the output of
'FFTW_R2HC'/'FFTW_HC2R' is otherwise exactly the same as for the
corresponding 1d r2c/c2r transform (i.e. 'FFTW_FORWARD'/'FFTW_BACKWARD'
transforms, respectively). Recall that these transforms are
unnormalized, so r2hc followed by hc2r will result in the original data
multiplied by 'n'. Furthermore, like the c2r transform, an out-of-place
hc2r transform will _destroy its input_ array.
Although these halfcomplex transforms can be used with the
multi-dimensional r2r interface, the interpretation of such a separable
product of transforms along each dimension is problematic. For example,
consider a two-dimensional 'n0' by 'n1', r2hc by r2hc transform planned
by 'fftw_plan_r2r_2d(n0, n1, in, out, FFTW_R2HC, FFTW_R2HC,
FFTW_MEASURE)'. Conceptually, FFTW first transforms the rows (of size
'n1') to produce halfcomplex rows, and then transforms the columns (of
size 'n0'). Half of these column transforms, however, are of imaginary
parts, and should therefore be multiplied by i and combined with the
r2hc transforms of the real columns to produce the 2d DFT amplitudes;
FFTW's r2r transform does _not_ perform this combination for you. Thus,
if a multi-dimensional real-input/output DFT is required, we recommend
using the ordinary r2c/c2r interface (Multi-Dimensional DFTs of
Real Data).