FFTW 3.3.8: More DFTs of Real Data

FFTW supports several other transform types via a unified r2r cannam@167: (real-to-real) interface, cannam@167: cannam@167: so called because it takes a real (double) array and outputs a cannam@167: real array of the same size. These r2r transforms currently fall into cannam@167: three categories: DFTs of real input and complex-Hermitian output in cannam@167: halfcomplex format, DFTs of real input with even/odd symmetry cannam@167: (a.k.a. discrete cosine/sine transforms, DCTs/DSTs), and discrete cannam@167: Hartley transforms (DHTs), all described in more detail by the cannam@167: following sections. cannam@167:

The r2r transforms follow the by now familiar interface of creating an cannam@167: fftw_plan, executing it with fftw_execute(plan), and cannam@167: destroying it with fftw_destroy_plan(plan). Furthermore, all cannam@167: r2r transforms share the same planner interface: cannam@167:

cannam@167:

fftw_plan fftw_plan_r2r_1d(int n, double *in, double *out,
cannam@167:                            fftw_r2r_kind kind, unsigned flags);
cannam@167: fftw_plan fftw_plan_r2r_2d(int n0, int n1, double *in, double *out,
cannam@167:                            fftw_r2r_kind kind0, fftw_r2r_kind kind1,
cannam@167:                            unsigned flags);
cannam@167: fftw_plan fftw_plan_r2r_3d(int n0, int n1, int n2,
cannam@167:                            double *in, double *out,
cannam@167:                            fftw_r2r_kind kind0,
cannam@167:                            fftw_r2r_kind kind1,
cannam@167:                            fftw_r2r_kind kind2,
cannam@167:                            unsigned flags);
cannam@167: fftw_plan fftw_plan_r2r(int rank, const int *n, double *in, double *out,
cannam@167:                         const fftw_r2r_kind *kind, unsigned flags);
cannam@167:

Just as for the complex DFT, these plan 1d/2d/3d/multi-dimensional cannam@167: transforms for contiguous arrays in row-major order, transforming (real) cannam@167: input to output of the same size, where n specifies the cannam@167: physical dimensions of the arrays. All positive n are cannam@167: supported (with the exception of n=1 for the FFTW_REDFT00 cannam@167: kind, noted in the real-even subsection below); products of small cannam@167: factors are most efficient (factorizing n-1 and n+1 for cannam@167: FFTW_REDFT00 and FFTW_RODFT00 kinds, described below), but cannam@167: an O(n log n) cannam@167: algorithm is used even for prime sizes. cannam@167:

Each dimension has a kind parameter, of type cannam@167: fftw_r2r_kind, specifying the kind of r2r transform to be used cannam@167: for that dimension. cannam@167: cannam@167: cannam@167: (In the case of fftw_plan_r2r, this is an array kind[rank] cannam@167: where kind[i] is the transform kind for the dimension cannam@167: n[i].) The kind can be one of a set of predefined constants, cannam@167: defined in the following subsections. cannam@167:

In other words, FFTW computes the separable product of the specified cannam@167: r2r transforms over each dimension, which can be used e.g. for partial cannam@167: differential equations with mixed boundary conditions. (For some r2r cannam@167: kinds, notably the halfcomplex DFT and the DHT, such a separable cannam@167: product is somewhat problematic in more than one dimension, however, cannam@167: as is described below.) cannam@167:

In the current version of FFTW, all r2r transforms except for the cannam@167: halfcomplex type are computed via pre- or post-processing of cannam@167: halfcomplex transforms, and they are therefore not as fast as they cannam@167: could be. Since most other general DCT/DST codes employ a similar cannam@167: algorithm, however, FFTW’s implementation should provide at least cannam@167: competitive performance. cannam@167:

• The Halfcomplex-format DFT:		cannam@167:
• Real even/odd DFTs (cosine/sine transforms):		cannam@167:
• The Discrete Hartley Transform:		cannam@167:

2.5 More DFTs of Real Data