Chris@19: Chris@19:
Chris@19:Chris@19: Previous: Multi-Dimensional DFTs of Real Data, Chris@19: Up: Tutorial Chris@19:
FFTW supports several other transform types via a unified r2r
Chris@19: (real-to-real) interface,
Chris@19: so called because it takes a real (double
) array and outputs a
Chris@19: real array of the same size. These r2r transforms currently fall into
Chris@19: three categories: DFTs of real input and complex-Hermitian output in
Chris@19: halfcomplex format, DFTs of real input with even/odd symmetry
Chris@19: (a.k.a. discrete cosine/sine transforms, DCTs/DSTs), and discrete
Chris@19: Hartley transforms (DHTs), all described in more detail by the
Chris@19: following sections.
Chris@19:
Chris@19:
The r2r transforms follow the by now familiar interface of creating an
Chris@19: fftw_plan
, executing it with fftw_execute(plan)
, and
Chris@19: destroying it with fftw_destroy_plan(plan)
. Furthermore, all
Chris@19: r2r transforms share the same planner interface:
Chris@19:
Chris@19:
fftw_plan fftw_plan_r2r_1d(int n, double *in, double *out, Chris@19: fftw_r2r_kind kind, unsigned flags); Chris@19: fftw_plan fftw_plan_r2r_2d(int n0, int n1, double *in, double *out, Chris@19: fftw_r2r_kind kind0, fftw_r2r_kind kind1, Chris@19: unsigned flags); Chris@19: fftw_plan fftw_plan_r2r_3d(int n0, int n1, int n2, Chris@19: double *in, double *out, Chris@19: fftw_r2r_kind kind0, Chris@19: fftw_r2r_kind kind1, Chris@19: fftw_r2r_kind kind2, Chris@19: unsigned flags); Chris@19: fftw_plan fftw_plan_r2r(int rank, const int *n, double *in, double *out, Chris@19: const fftw_r2r_kind *kind, unsigned flags); Chris@19:Chris@19:
Chris@19: Just as for the complex DFT, these plan 1d/2d/3d/multi-dimensional
Chris@19: transforms for contiguous arrays in row-major order, transforming (real)
Chris@19: input to output of the same size, where n
specifies the
Chris@19: physical dimensions of the arrays. All positive n
are
Chris@19: supported (with the exception of n=1
for the FFTW_REDFT00
Chris@19: kind, noted in the real-even subsection below); products of small
Chris@19: factors are most efficient (factorizing n-1
and n+1
for
Chris@19: FFTW_REDFT00
and FFTW_RODFT00
kinds, described below), but
Chris@19: an O(n log n) algorithm is used even for prime sizes.
Chris@19:
Chris@19:
Each dimension has a kind parameter, of type
Chris@19: fftw_r2r_kind
, specifying the kind of r2r transform to be used
Chris@19: for that dimension.
Chris@19: (In the case of fftw_plan_r2r
, this is an array kind[rank]
Chris@19: where kind[i]
is the transform kind for the dimension
Chris@19: n[i]
.) The kind can be one of a set of predefined constants,
Chris@19: defined in the following subsections.
Chris@19:
Chris@19:
In other words, FFTW computes the separable product of the specified Chris@19: r2r transforms over each dimension, which can be used e.g. for partial Chris@19: differential equations with mixed boundary conditions. (For some r2r Chris@19: kinds, notably the halfcomplex DFT and the DHT, such a separable Chris@19: product is somewhat problematic in more than one dimension, however, Chris@19: as is described below.) Chris@19: Chris@19:
In the current version of FFTW, all r2r transforms except for the Chris@19: halfcomplex type are computed via pre- or post-processing of Chris@19: halfcomplex transforms, and they are therefore not as fast as they Chris@19: could be. Since most other general DCT/DST codes employ a similar Chris@19: algorithm, however, FFTW's implementation should provide at least Chris@19: competitive performance. Chris@19: Chris@19: Chris@19: Chris@19: