cannam@167: @node Tutorial, Other Important Topics, Introduction, Top cannam@167: @chapter Tutorial cannam@167: @menu cannam@167: * Complex One-Dimensional DFTs:: cannam@167: * Complex Multi-Dimensional DFTs:: cannam@167: * One-Dimensional DFTs of Real Data:: cannam@167: * Multi-Dimensional DFTs of Real Data:: cannam@167: * More DFTs of Real Data:: cannam@167: @end menu cannam@167: cannam@167: This chapter describes the basic usage of FFTW, i.e., how to compute cannam@167: @cindex basic interface cannam@167: the Fourier transform of a single array. This chapter tells the cannam@167: truth, but not the @emph{whole} truth. Specifically, FFTW implements cannam@167: additional routines and flags that are not documented here, although cannam@167: in many cases we try to indicate where added capabilities exist. For cannam@167: more complete information, see @ref{FFTW Reference}. (Note that you cannam@167: need to compile and install FFTW before you can use it in a program. cannam@167: For the details of the installation, see @ref{Installation and cannam@167: Customization}.) cannam@167: cannam@167: We recommend that you read this tutorial in order.@footnote{You can cannam@167: read the tutorial in bit-reversed order after computing your first cannam@167: transform.} At the least, read the first section (@pxref{Complex cannam@167: One-Dimensional DFTs}) before reading any of the others, even if your cannam@167: main interest lies in one of the other transform types. cannam@167: cannam@167: Users of FFTW version 2 and earlier may also want to read @ref{Upgrading cannam@167: from FFTW version 2}. cannam@167: cannam@167: @c ------------------------------------------------------------ cannam@167: @node Complex One-Dimensional DFTs, Complex Multi-Dimensional DFTs, Tutorial, Tutorial cannam@167: @section Complex One-Dimensional DFTs cannam@167: cannam@167: @quotation cannam@167: Plan: To bother about the best method of accomplishing an accidental result. cannam@167: [Ambrose Bierce, @cite{The Enlarged Devil's Dictionary}.] cannam@167: @cindex Devil cannam@167: @end quotation cannam@167: cannam@167: @iftex cannam@167: @medskip cannam@167: @end iftex cannam@167: cannam@167: The basic usage of FFTW to compute a one-dimensional DFT of size cannam@167: @code{N} is simple, and it typically looks something like this code: cannam@167: cannam@167: @example cannam@167: #include cannam@167: ... cannam@167: @{ cannam@167: fftw_complex *in, *out; cannam@167: fftw_plan p; cannam@167: ... cannam@167: in = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N); cannam@167: out = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N); cannam@167: p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE); cannam@167: ... cannam@167: fftw_execute(p); /* @r{repeat as needed} */ cannam@167: ... cannam@167: fftw_destroy_plan(p); cannam@167: fftw_free(in); fftw_free(out); cannam@167: @} cannam@167: @end example cannam@167: cannam@167: You must link this code with the @code{fftw3} library. On Unix systems, cannam@167: link with @code{-lfftw3 -lm}. cannam@167: cannam@167: The example code first allocates the input and output arrays. You can cannam@167: allocate them in any way that you like, but we recommend using cannam@167: @code{fftw_malloc}, which behaves like cannam@167: @findex fftw_malloc cannam@167: @code{malloc} except that it properly aligns the array when SIMD cannam@167: instructions (such as SSE and Altivec) are available (@pxref{SIMD cannam@167: alignment and fftw_malloc}). [Alternatively, we provide a convenient wrapper function @code{fftw_alloc_complex(N)} which has the same effect.] cannam@167: @findex fftw_alloc_complex cannam@167: @cindex SIMD cannam@167: cannam@167: cannam@167: The data is an array of type @code{fftw_complex}, which is by default a cannam@167: @code{double[2]} composed of the real (@code{in[i][0]}) and imaginary cannam@167: (@code{in[i][1]}) parts of a complex number. cannam@167: @tindex fftw_complex cannam@167: cannam@167: The next step is to create a @dfn{plan}, which is an object cannam@167: @cindex plan cannam@167: that contains all the data that FFTW needs to compute the FFT. cannam@167: This function creates the plan: cannam@167: cannam@167: @example cannam@167: fftw_plan fftw_plan_dft_1d(int n, fftw_complex *in, fftw_complex *out, cannam@167: int sign, unsigned flags); cannam@167: @end example cannam@167: @findex fftw_plan_dft_1d cannam@167: @tindex fftw_plan cannam@167: cannam@167: The first argument, @code{n}, is the size of the transform you are cannam@167: trying to compute. The size @code{n} can be any positive integer, but cannam@167: sizes that are products of small factors are transformed most cannam@167: efficiently (although prime sizes still use an @Onlogn{} algorithm). cannam@167: cannam@167: The next two arguments are pointers to the input and output arrays of cannam@167: the transform. These pointers can be equal, indicating an cannam@167: @dfn{in-place} transform. cannam@167: @cindex in-place cannam@167: cannam@167: cannam@167: The fourth argument, @code{sign}, can be either @code{FFTW_FORWARD} cannam@167: (@code{-1}) or @code{FFTW_BACKWARD} (@code{+1}), cannam@167: @ctindex FFTW_FORWARD cannam@167: @ctindex FFTW_BACKWARD cannam@167: and indicates the direction of the transform you are interested in; cannam@167: technically, it is the sign of the exponent in the transform. cannam@167: cannam@167: The @code{flags} argument is usually either @code{FFTW_MEASURE} or cannam@167: @cindex flags cannam@167: @code{FFTW_ESTIMATE}. @code{FFTW_MEASURE} instructs FFTW to run cannam@167: @ctindex FFTW_MEASURE cannam@167: and measure the execution time of several FFTs in order to find the cannam@167: best way to compute the transform of size @code{n}. This process takes cannam@167: some time (usually a few seconds), depending on your machine and on cannam@167: the size of the transform. @code{FFTW_ESTIMATE}, on the contrary, cannam@167: does not run any computation and just builds a cannam@167: @ctindex FFTW_ESTIMATE cannam@167: reasonable plan that is probably sub-optimal. In short, if your cannam@167: program performs many transforms of the same size and initialization cannam@167: time is not important, use @code{FFTW_MEASURE}; otherwise use the cannam@167: estimate. cannam@167: cannam@167: @emph{You must create the plan before initializing the input}, because cannam@167: @code{FFTW_MEASURE} overwrites the @code{in}/@code{out} arrays. cannam@167: (Technically, @code{FFTW_ESTIMATE} does not touch your arrays, but you cannam@167: should always create plans first just to be sure.) cannam@167: cannam@167: Once the plan has been created, you can use it as many times as you cannam@167: like for transforms on the specified @code{in}/@code{out} arrays, cannam@167: computing the actual transforms via @code{fftw_execute(plan)}: cannam@167: @example cannam@167: void fftw_execute(const fftw_plan plan); cannam@167: @end example cannam@167: @findex fftw_execute cannam@167: cannam@167: The DFT results are stored in-order in the array @code{out}, with the cannam@167: zero-frequency (DC) component in @code{out[0]}. cannam@167: @cindex frequency cannam@167: If @code{in != out}, the transform is @dfn{out-of-place} and the input cannam@167: array @code{in} is not modified. Otherwise, the input array is cannam@167: overwritten with the transform. cannam@167: cannam@167: @cindex execute cannam@167: If you want to transform a @emph{different} array of the same size, you cannam@167: can create a new plan with @code{fftw_plan_dft_1d} and FFTW cannam@167: automatically reuses the information from the previous plan, if cannam@167: possible. Alternatively, with the ``guru'' interface you can apply a cannam@167: given plan to a different array, if you are careful. cannam@167: @xref{FFTW Reference}. cannam@167: cannam@167: When you are done with the plan, you deallocate it by calling cannam@167: @code{fftw_destroy_plan(plan)}: cannam@167: @example cannam@167: void fftw_destroy_plan(fftw_plan plan); cannam@167: @end example cannam@167: @findex fftw_destroy_plan cannam@167: If you allocate an array with @code{fftw_malloc()} you must deallocate cannam@167: it with @code{fftw_free()}. Do not use @code{free()} or, heaven cannam@167: forbid, @code{delete}. cannam@167: @findex fftw_free cannam@167: cannam@167: FFTW computes an @emph{unnormalized} DFT. Thus, computing a forward cannam@167: followed by a backward transform (or vice versa) results in the original cannam@167: array scaled by @code{n}. For the definition of the DFT, see @ref{What cannam@167: FFTW Really Computes}. cannam@167: @cindex DFT cannam@167: @cindex normalization cannam@167: cannam@167: cannam@167: If you have a C compiler, such as @code{gcc}, that supports the cannam@167: C99 standard, and you @code{#include } @emph{before} cannam@167: @code{}, then @code{fftw_complex} is the native cannam@167: double-precision complex type and you can manipulate it with ordinary cannam@167: arithmetic. Otherwise, FFTW defines its own complex type, which is cannam@167: bit-compatible with the C99 complex type. @xref{Complex numbers}. cannam@167: (The C++ @code{} template class may also be usable via a cannam@167: typecast.) cannam@167: @cindex C++ cannam@167: cannam@167: To use single or long-double precision versions of FFTW, replace the cannam@167: @code{fftw_} prefix by @code{fftwf_} or @code{fftwl_} and link with cannam@167: @code{-lfftw3f} or @code{-lfftw3l}, but use the @emph{same} cannam@167: @code{} header file. cannam@167: @cindex precision cannam@167: cannam@167: cannam@167: Many more flags exist besides @code{FFTW_MEASURE} and cannam@167: @code{FFTW_ESTIMATE}. For example, use @code{FFTW_PATIENT} if you're cannam@167: willing to wait even longer for a possibly even faster plan (@pxref{FFTW cannam@167: Reference}). cannam@167: @ctindex FFTW_PATIENT cannam@167: You can also save plans for future use, as described by @ref{Words of cannam@167: Wisdom-Saving Plans}. cannam@167: cannam@167: @c ------------------------------------------------------------ cannam@167: @node Complex Multi-Dimensional DFTs, One-Dimensional DFTs of Real Data, Complex One-Dimensional DFTs, Tutorial cannam@167: @section Complex Multi-Dimensional DFTs cannam@167: cannam@167: Multi-dimensional transforms work much the same way as one-dimensional cannam@167: transforms: you allocate arrays of @code{fftw_complex} (preferably cannam@167: using @code{fftw_malloc}), create an @code{fftw_plan}, execute it as cannam@167: many times as you want with @code{fftw_execute(plan)}, and clean up cannam@167: with @code{fftw_destroy_plan(plan)} (and @code{fftw_free}). cannam@167: cannam@167: FFTW provides two routines for creating plans for 2d and 3d transforms, cannam@167: and one routine for creating plans of arbitrary dimensionality. cannam@167: The 2d and 3d routines have the following signature: cannam@167: @example cannam@167: fftw_plan fftw_plan_dft_2d(int n0, int n1, cannam@167: fftw_complex *in, fftw_complex *out, cannam@167: int sign, unsigned flags); cannam@167: fftw_plan fftw_plan_dft_3d(int n0, int n1, int n2, cannam@167: fftw_complex *in, fftw_complex *out, cannam@167: int sign, unsigned flags); cannam@167: @end example cannam@167: @findex fftw_plan_dft_2d cannam@167: @findex fftw_plan_dft_3d cannam@167: cannam@167: These routines create plans for @code{n0} by @code{n1} two-dimensional cannam@167: (2d) transforms and @code{n0} by @code{n1} by @code{n2} 3d transforms, cannam@167: respectively. All of these transforms operate on contiguous arrays in cannam@167: the C-standard @dfn{row-major} order, so that the last dimension has the cannam@167: fastest-varying index in the array. This layout is described further in cannam@167: @ref{Multi-dimensional Array Format}. cannam@167: cannam@167: FFTW can also compute transforms of higher dimensionality. In order to cannam@167: avoid confusion between the various meanings of the the word cannam@167: ``dimension'', we use the term @emph{rank} cannam@167: @cindex rank cannam@167: to denote the number of independent indices in an array.@footnote{The cannam@167: term ``rank'' is commonly used in the APL, FORTRAN, and Common Lisp cannam@167: traditions, although it is not so common in the C@tie{}world.} For cannam@167: example, we say that a 2d transform has rank@tie{}2, a 3d transform has cannam@167: rank@tie{}3, and so on. You can plan transforms of arbitrary rank by cannam@167: means of the following function: cannam@167: cannam@167: @example cannam@167: fftw_plan fftw_plan_dft(int rank, const int *n, cannam@167: fftw_complex *in, fftw_complex *out, cannam@167: int sign, unsigned flags); cannam@167: @end example cannam@167: @findex fftw_plan_dft cannam@167: cannam@167: Here, @code{n} is a pointer to an array @code{n[rank]} denoting an cannam@167: @code{n[0]} by @code{n[1]} by @dots{} by @code{n[rank-1]} transform. cannam@167: Thus, for example, the call cannam@167: @example cannam@167: fftw_plan_dft_2d(n0, n1, in, out, sign, flags); cannam@167: @end example cannam@167: is equivalent to the following code fragment: cannam@167: @example cannam@167: int n[2]; cannam@167: n[0] = n0; cannam@167: n[1] = n1; cannam@167: fftw_plan_dft(2, n, in, out, sign, flags); cannam@167: @end example cannam@167: @code{fftw_plan_dft} is not restricted to 2d and 3d transforms, cannam@167: however, but it can plan transforms of arbitrary rank. cannam@167: cannam@167: You may have noticed that all the planner routines described so far cannam@167: have overlapping functionality. For example, you can plan a 1d or 2d cannam@167: transform by using @code{fftw_plan_dft} with a @code{rank} of @code{1} cannam@167: or @code{2}, or even by calling @code{fftw_plan_dft_3d} with @code{n0} cannam@167: and/or @code{n1} equal to @code{1} (with no loss in efficiency). This cannam@167: pattern continues, and FFTW's planning routines in general form a cannam@167: ``partial order,'' sequences of cannam@167: @cindex partial order cannam@167: interfaces with strictly increasing generality but correspondingly cannam@167: greater complexity. cannam@167: cannam@167: @code{fftw_plan_dft} is the most general complex-DFT routine that we cannam@167: describe in this tutorial, but there are also the advanced and guru interfaces, cannam@167: @cindex advanced interface cannam@167: @cindex guru interface cannam@167: which allow one to efficiently combine multiple/strided transforms cannam@167: into a single FFTW plan, transform a subset of a larger cannam@167: multi-dimensional array, and/or to handle more general complex-number cannam@167: formats. For more information, see @ref{FFTW Reference}. cannam@167: cannam@167: @c ------------------------------------------------------------ cannam@167: @node One-Dimensional DFTs of Real Data, Multi-Dimensional DFTs of Real Data, Complex Multi-Dimensional DFTs, Tutorial cannam@167: @section One-Dimensional DFTs of Real Data cannam@167: cannam@167: In many practical applications, the input data @code{in[i]} are purely cannam@167: real numbers, in which case the DFT output satisfies the ``Hermitian'' cannam@167: @cindex Hermitian cannam@167: redundancy: @code{out[i]} is the conjugate of @code{out[n-i]}. It is cannam@167: possible to take advantage of these circumstances in order to achieve cannam@167: roughly a factor of two improvement in both speed and memory usage. cannam@167: cannam@167: In exchange for these speed and space advantages, the user sacrifices cannam@167: some of the simplicity of FFTW's complex transforms. First of all, the cannam@167: input and output arrays are of @emph{different sizes and types}: the cannam@167: input is @code{n} real numbers, while the output is @code{n/2+1} cannam@167: complex numbers (the non-redundant outputs); this also requires slight cannam@167: ``padding'' of the input array for cannam@167: @cindex padding cannam@167: in-place transforms. Second, the inverse transform (complex to real) cannam@167: has the side-effect of @emph{overwriting its input array}, by default. cannam@167: Neither of these inconveniences should pose a serious problem for cannam@167: users, but it is important to be aware of them. cannam@167: cannam@167: The routines to perform real-data transforms are almost the same as cannam@167: those for complex transforms: you allocate arrays of @code{double} cannam@167: and/or @code{fftw_complex} (preferably using @code{fftw_malloc} or cannam@167: @code{fftw_alloc_complex}), create an @code{fftw_plan}, execute it as cannam@167: many times as you want with @code{fftw_execute(plan)}, and clean up cannam@167: with @code{fftw_destroy_plan(plan)} (and @code{fftw_free}). The only cannam@167: differences are that the input (or output) is of type @code{double} cannam@167: and there are new routines to create the plan. In one dimension: cannam@167: cannam@167: @example cannam@167: fftw_plan fftw_plan_dft_r2c_1d(int n, double *in, fftw_complex *out, cannam@167: unsigned flags); cannam@167: fftw_plan fftw_plan_dft_c2r_1d(int n, fftw_complex *in, double *out, cannam@167: unsigned flags); cannam@167: @end example cannam@167: @findex fftw_plan_dft_r2c_1d cannam@167: @findex fftw_plan_dft_c2r_1d cannam@167: cannam@167: for the real input to complex-Hermitian output (@dfn{r2c}) and cannam@167: complex-Hermitian input to real output (@dfn{c2r}) transforms. cannam@167: @cindex r2c cannam@167: @cindex c2r cannam@167: Unlike the complex DFT planner, there is no @code{sign} argument. cannam@167: Instead, r2c DFTs are always @code{FFTW_FORWARD} and c2r DFTs are cannam@167: always @code{FFTW_BACKWARD}. cannam@167: @ctindex FFTW_FORWARD cannam@167: @ctindex FFTW_BACKWARD cannam@167: (For single/long-double precision cannam@167: @code{fftwf} and @code{fftwl}, @code{double} should be replaced by cannam@167: @code{float} and @code{long double}, respectively.) cannam@167: @cindex precision cannam@167: cannam@167: cannam@167: Here, @code{n} is the ``logical'' size of the DFT, not necessarily the cannam@167: physical size of the array. In particular, the real (@code{double}) cannam@167: array has @code{n} elements, while the complex (@code{fftw_complex}) cannam@167: array has @code{n/2+1} elements (where the division is rounded down). cannam@167: For an in-place transform, cannam@167: @cindex in-place cannam@167: @code{in} and @code{out} are aliased to the same array, which must be cannam@167: big enough to hold both; so, the real array would actually have cannam@167: @code{2*(n/2+1)} elements, where the elements beyond the first cannam@167: @code{n} are unused padding. (Note that this is very different from cannam@167: the concept of ``zero-padding'' a transform to a larger length, which cannam@167: changes the logical size of the DFT by actually adding new input cannam@167: data.) The @math{k}th element of the complex array is exactly the cannam@167: same as the @math{k}th element of the corresponding complex DFT. All cannam@167: positive @code{n} are supported; products of small factors are most cannam@167: efficient, but an @Onlogn algorithm is used even for prime sizes. cannam@167: cannam@167: As noted above, the c2r transform destroys its input array even for cannam@167: out-of-place transforms. This can be prevented, if necessary, by cannam@167: including @code{FFTW_PRESERVE_INPUT} in the @code{flags}, with cannam@167: unfortunately some sacrifice in performance. cannam@167: @cindex flags cannam@167: @ctindex FFTW_PRESERVE_INPUT cannam@167: This flag is also not currently supported for multi-dimensional real cannam@167: DFTs (next section). cannam@167: cannam@167: Readers familiar with DFTs of real data will recall that the 0th (the cannam@167: ``DC'') and @code{n/2}-th (the ``Nyquist'' frequency, when @code{n} is cannam@167: even) elements of the complex output are purely real. Some cannam@167: implementations therefore store the Nyquist element where the DC cannam@167: imaginary part would go, in order to make the input and output arrays cannam@167: the same size. Such packing, however, does not generalize well to cannam@167: multi-dimensional transforms, and the space savings are miniscule in cannam@167: any case; FFTW does not support it. cannam@167: cannam@167: An alternative interface for one-dimensional r2c and c2r DFTs can be cannam@167: found in the @samp{r2r} interface (@pxref{The Halfcomplex-format cannam@167: DFT}), with ``halfcomplex''-format output that @emph{is} the same size cannam@167: (and type) as the input array. cannam@167: @cindex halfcomplex format cannam@167: That interface, although it is not very useful for multi-dimensional cannam@167: transforms, may sometimes yield better performance. cannam@167: cannam@167: @c ------------------------------------------------------------ cannam@167: @node Multi-Dimensional DFTs of Real Data, More DFTs of Real Data, One-Dimensional DFTs of Real Data, Tutorial cannam@167: @section Multi-Dimensional DFTs of Real Data cannam@167: cannam@167: Multi-dimensional DFTs of real data use the following planner routines: cannam@167: cannam@167: @example cannam@167: fftw_plan fftw_plan_dft_r2c_2d(int n0, int n1, cannam@167: double *in, fftw_complex *out, cannam@167: unsigned flags); cannam@167: fftw_plan fftw_plan_dft_r2c_3d(int n0, int n1, int n2, cannam@167: double *in, fftw_complex *out, cannam@167: unsigned flags); cannam@167: fftw_plan fftw_plan_dft_r2c(int rank, const int *n, cannam@167: double *in, fftw_complex *out, cannam@167: unsigned flags); cannam@167: @end example cannam@167: @findex fftw_plan_dft_r2c_2d cannam@167: @findex fftw_plan_dft_r2c_3d cannam@167: @findex fftw_plan_dft_r2c cannam@167: cannam@167: as well as the corresponding @code{c2r} routines with the input/output cannam@167: types swapped. These routines work similarly to their complex cannam@167: analogues, except for the fact that here the complex output array is cut cannam@167: roughly in half and the real array requires padding for in-place cannam@167: transforms (as in 1d, above). cannam@167: cannam@167: As before, @code{n} is the logical size of the array, and the cannam@167: consequences of this on the the format of the complex arrays deserve cannam@167: careful attention. cannam@167: @cindex r2c/c2r multi-dimensional array format cannam@167: Suppose that the real data has dimensions @ndims (in row-major order). cannam@167: Then, after an r2c transform, the output is an @ndimshalf array of cannam@167: @code{fftw_complex} values in row-major order, corresponding to slightly cannam@167: over half of the output of the corresponding complex DFT. (The division cannam@167: is rounded down.) The ordering of the data is otherwise exactly the cannam@167: same as in the complex-DFT case. cannam@167: cannam@167: For out-of-place transforms, this is the end of the story: the real cannam@167: data is stored as a row-major array of size @ndims and the complex cannam@167: data is stored as a row-major array of size @ndimshalf{}. cannam@167: cannam@167: For in-place transforms, however, extra padding of the real-data array cannam@167: is necessary because the complex array is larger than the real array, cannam@167: and the two arrays share the same memory locations. Thus, for cannam@167: in-place transforms, the final dimension of the real-data array must cannam@167: be padded with extra values to accommodate the size of the complex cannam@167: data---two values if the last dimension is even and one if it is odd. cannam@167: @cindex padding cannam@167: That is, the last dimension of the real data must physically contain cannam@167: @tex cannam@167: $2 (n_{d-1}/2+1)$ cannam@167: @end tex cannam@167: @ifinfo cannam@167: 2 * (n[d-1]/2+1) cannam@167: @end ifinfo cannam@167: @html cannam@167: 2 * (nd-1/2+1) cannam@167: @end html cannam@167: @code{double} values (exactly enough to hold the complex data). cannam@167: This physical array size does not, however, change the @emph{logical} cannam@167: array size---only cannam@167: @tex cannam@167: $n_{d-1}$ cannam@167: @end tex cannam@167: @ifinfo cannam@167: n[d-1] cannam@167: @end ifinfo cannam@167: @html cannam@167: nd-1 cannam@167: @end html cannam@167: values are actually stored in the last dimension, and cannam@167: @tex cannam@167: $n_{d-1}$ cannam@167: @end tex cannam@167: @ifinfo cannam@167: n[d-1] cannam@167: @end ifinfo cannam@167: @html cannam@167: nd-1 cannam@167: @end html cannam@167: is the last dimension passed to the plan-creation routine. cannam@167: cannam@167: For example, consider the transform of a two-dimensional real array of cannam@167: size @code{n0} by @code{n1}. The output of the r2c transform is a cannam@167: two-dimensional complex array of size @code{n0} by @code{n1/2+1}, where cannam@167: the @code{y} dimension has been cut nearly in half because of cannam@167: redundancies in the output. Because @code{fftw_complex} is twice the cannam@167: size of @code{double}, the output array is slightly bigger than the cannam@167: input array. Thus, if we want to compute the transform in place, we cannam@167: must @emph{pad} the input array so that it is of size @code{n0} by cannam@167: @code{2*(n1/2+1)}. If @code{n1} is even, then there are two padding cannam@167: elements at the end of each row (which need not be initialized, as they cannam@167: are only used for output). cannam@167: cannam@167: @ifhtml cannam@167: The following illustration depicts the input and output arrays just cannam@167: described, for both the out-of-place and in-place transforms (with the cannam@167: arrows indicating consecutive memory locations): cannam@167: @image{rfftwnd-for-html} cannam@167: @end ifhtml cannam@167: @ifnotinfo cannam@167: @ifnothtml cannam@167: @float Figure,fig:rfftwnd cannam@167: @center @image{rfftwnd} cannam@167: @caption{Illustration of the data layout for a 2d @code{nx} by @code{ny} cannam@167: real-to-complex transform.} cannam@167: @end float cannam@167: @ref{fig:rfftwnd} depicts the input and output arrays just cannam@167: described, for both the out-of-place and in-place transforms (with the cannam@167: arrows indicating consecutive memory locations): cannam@167: @end ifnothtml cannam@167: @end ifnotinfo cannam@167: cannam@167: These transforms are unnormalized, so an r2c followed by a c2r cannam@167: transform (or vice versa) will result in the original data scaled by cannam@167: the number of real data elements---that is, the product of the cannam@167: (logical) dimensions of the real data. cannam@167: @cindex normalization cannam@167: cannam@167: cannam@167: (Because the last dimension is treated specially, if it is equal to cannam@167: @code{1} the transform is @emph{not} equivalent to a lower-dimensional cannam@167: r2c/c2r transform. In that case, the last complex dimension also has cannam@167: size @code{1} (@code{=1/2+1}), and no advantage is gained over the cannam@167: complex transforms.) cannam@167: cannam@167: @c ------------------------------------------------------------ cannam@167: @node More DFTs of Real Data, , Multi-Dimensional DFTs of Real Data, Tutorial cannam@167: @section More DFTs of Real Data cannam@167: @menu cannam@167: * The Halfcomplex-format DFT:: cannam@167: * Real even/odd DFTs (cosine/sine transforms):: cannam@167: * The Discrete Hartley Transform:: cannam@167: @end menu cannam@167: cannam@167: FFTW supports several other transform types via a unified @dfn{r2r} cannam@167: (real-to-real) interface, cannam@167: @cindex r2r cannam@167: so called because it takes a real (@code{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: cannam@167: The r2r transforms follow the by now familiar interface of creating an cannam@167: @code{fftw_plan}, executing it with @code{fftw_execute(plan)}, and cannam@167: destroying it with @code{fftw_destroy_plan(plan)}. Furthermore, all cannam@167: r2r transforms share the same planner interface: cannam@167: cannam@167: @example 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: @end example cannam@167: @findex fftw_plan_r2r_1d cannam@167: @findex fftw_plan_r2r_2d cannam@167: @findex fftw_plan_r2r_3d cannam@167: @findex fftw_plan_r2r cannam@167: 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 @code{n} specifies the cannam@167: @emph{physical} dimensions of the arrays. All positive @code{n} are cannam@167: supported (with the exception of @code{n=1} for the @code{FFTW_REDFT00} cannam@167: kind, noted in the real-even subsection below); products of small cannam@167: factors are most efficient (factorizing @code{n-1} and @code{n+1} for cannam@167: @code{FFTW_REDFT00} and @code{FFTW_RODFT00} kinds, described below), but cannam@167: an @Onlogn algorithm is used even for prime sizes. cannam@167: cannam@167: Each dimension has a @dfn{kind} parameter, of type cannam@167: @code{fftw_r2r_kind}, specifying the kind of r2r transform to be used cannam@167: for that dimension. cannam@167: @cindex kind (r2r) cannam@167: @tindex fftw_r2r_kind cannam@167: (In the case of @code{fftw_plan_r2r}, this is an array @code{kind[rank]} cannam@167: where @code{kind[i]} is the transform kind for the dimension cannam@167: @code{n[i]}.) The kind can be one of a set of predefined constants, cannam@167: defined in the following subsections. cannam@167: 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: 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: cannam@167: @c =========> cannam@167: @node The Halfcomplex-format DFT, Real even/odd DFTs (cosine/sine transforms), More DFTs of Real Data, More DFTs of Real Data cannam@167: @subsection The Halfcomplex-format DFT cannam@167: cannam@167: An r2r kind of @code{FFTW_R2HC} (@dfn{r2hc}) corresponds to an r2c DFT cannam@167: @ctindex FFTW_R2HC cannam@167: @cindex r2c cannam@167: @cindex r2hc cannam@167: (@pxref{One-Dimensional DFTs of Real Data}) but with ``halfcomplex'' cannam@167: format output, and may sometimes be faster and/or more convenient than cannam@167: the latter. cannam@167: @cindex halfcomplex format cannam@167: The inverse @dfn{hc2r} transform is of kind @code{FFTW_HC2R}. cannam@167: @ctindex FFTW_HC2R cannam@167: @cindex hc2r cannam@167: This consists of the non-redundant half of the complex output for a 1d cannam@167: real-input DFT of size @code{n}, stored as a sequence of @code{n} real cannam@167: numbers (@code{double}) in the format: cannam@167: cannam@167: @tex cannam@167: $$ cannam@167: r_0, r_1, r_2, \ldots, r_{n/2}, i_{(n+1)/2-1}, \ldots, i_2, i_1 cannam@167: $$ cannam@167: @end tex cannam@167: @ifinfo cannam@167: r0, r1, r2, r(n/2), i((n+1)/2-1), ..., i2, i1 cannam@167: @end ifinfo cannam@167: @html cannam@167:

cannam@167: r0, r1, r2, ..., rn/2, i(n+1)/2-1, ..., i2, i1 cannam@167:

cannam@167: @end html cannam@167: cannam@167: Here, cannam@167: @ifinfo cannam@167: rk cannam@167: @end ifinfo cannam@167: @tex cannam@167: $r_k$ cannam@167: @end tex cannam@167: @html cannam@167: rk cannam@167: @end html cannam@167: is the real part of the @math{k}th output, and cannam@167: @ifinfo cannam@167: ik cannam@167: @end ifinfo cannam@167: @tex cannam@167: $i_k$ cannam@167: @end tex cannam@167: @html cannam@167: ik cannam@167: @end html cannam@167: is the imaginary part. (Division by 2 is rounded down.) For a cannam@167: halfcomplex array @code{hc[n]}, the @math{k}th component thus has its cannam@167: real part in @code{hc[k]} and its imaginary part in @code{hc[n-k]}, with cannam@167: the exception of @code{k} @code{==} @code{0} or @code{n/2} (the latter cannam@167: only if @code{n} is even)---in these two cases, the imaginary part is cannam@167: zero due to symmetries of the real-input DFT, and is not stored. cannam@167: Thus, the r2hc transform of @code{n} real values is a halfcomplex array of cannam@167: length @code{n}, and vice versa for hc2r. cannam@167: @cindex normalization cannam@167: cannam@167: cannam@167: Aside from the differing format, the output of cannam@167: @code{FFTW_R2HC}/@code{FFTW_HC2R} is otherwise exactly the same as for cannam@167: the corresponding 1d r2c/c2r transform cannam@167: (i.e. @code{FFTW_FORWARD}/@code{FFTW_BACKWARD} transforms, respectively). cannam@167: Recall that these transforms are unnormalized, so r2hc followed by hc2r cannam@167: will result in the original data multiplied by @code{n}. Furthermore, cannam@167: like the c2r transform, an out-of-place hc2r transform will cannam@167: @emph{destroy its input} array. cannam@167: cannam@167: Although these halfcomplex transforms can be used with the cannam@167: multi-dimensional r2r interface, the interpretation of such a separable cannam@167: product of transforms along each dimension is problematic. For example, cannam@167: consider a two-dimensional @code{n0} by @code{n1}, r2hc by r2hc cannam@167: transform planned by @code{fftw_plan_r2r_2d(n0, n1, in, out, FFTW_R2HC, cannam@167: FFTW_R2HC, FFTW_MEASURE)}. Conceptually, FFTW first transforms the rows cannam@167: (of size @code{n1}) to produce halfcomplex rows, and then transforms the cannam@167: columns (of size @code{n0}). Half of these column transforms, however, cannam@167: are of imaginary parts, and should therefore be multiplied by @math{i} cannam@167: and combined with the r2hc transforms of the real columns to produce the cannam@167: 2d DFT amplitudes; FFTW's r2r transform does @emph{not} perform this cannam@167: combination for you. Thus, if a multi-dimensional real-input/output DFT cannam@167: is required, we recommend using the ordinary r2c/c2r cannam@167: interface (@pxref{Multi-Dimensional DFTs of Real Data}). cannam@167: cannam@167: @c =========> cannam@167: @node Real even/odd DFTs (cosine/sine transforms), The Discrete Hartley Transform, The Halfcomplex-format DFT, More DFTs of Real Data cannam@167: @subsection Real even/odd DFTs (cosine/sine transforms) cannam@167: cannam@167: The Fourier transform of a real-even function @math{f(-x) = f(x)} is cannam@167: real-even, and @math{i} times the Fourier transform of a real-odd cannam@167: function @math{f(-x) = -f(x)} is real-odd. Similar results hold for a cannam@167: discrete Fourier transform, and thus for these symmetries the need for cannam@167: complex inputs/outputs is entirely eliminated. Moreover, one gains a cannam@167: factor of two in speed/space from the fact that the data are real, and cannam@167: an additional factor of two from the even/odd symmetry: only the cannam@167: non-redundant (first) half of the array need be stored. The result is cannam@167: the real-even DFT (@dfn{REDFT}) and the real-odd DFT (@dfn{RODFT}), also cannam@167: known as the discrete cosine and sine transforms (@dfn{DCT} and cannam@167: @dfn{DST}), respectively. cannam@167: @cindex real-even DFT cannam@167: @cindex REDFT cannam@167: @cindex real-odd DFT cannam@167: @cindex RODFT cannam@167: @cindex discrete cosine transform cannam@167: @cindex DCT cannam@167: @cindex discrete sine transform cannam@167: @cindex DST cannam@167: cannam@167: cannam@167: (In this section, we describe the 1d transforms; multi-dimensional cannam@167: transforms are just a separable product of these transforms operating cannam@167: along each dimension.) cannam@167: cannam@167: Because of the discrete sampling, one has an additional choice: is the cannam@167: data even/odd around a sampling point, or around the point halfway cannam@167: between two samples? The latter corresponds to @emph{shifting} the cannam@167: samples by @emph{half} an interval, and gives rise to several transform cannam@167: variants denoted by REDFT@math{ab} and RODFT@math{ab}: @math{a} and cannam@167: @math{b} are @math{0} or @math{1}, and indicate whether the input cannam@167: (@math{a}) and/or output (@math{b}) are shifted by half a sample cannam@167: (@math{1} means it is shifted). These are also known as types I-IV of cannam@167: the DCT and DST, and all four types are supported by FFTW's r2r cannam@167: interface.@footnote{There are also type V-VIII transforms, which cannam@167: correspond to a logical DFT of @emph{odd} size @math{N}, independent of cannam@167: whether the physical size @code{n} is odd, but we do not support these cannam@167: variants.} cannam@167: cannam@167: The r2r kinds for the various REDFT and RODFT types supported by FFTW, cannam@167: along with the boundary conditions at both ends of the @emph{input} cannam@167: array (@code{n} real numbers @code{in[j=0..n-1]}), are: cannam@167: cannam@167: @itemize @bullet cannam@167: cannam@167: @item cannam@167: @code{FFTW_REDFT00} (DCT-I): even around @math{j=0} and even around @math{j=n-1}. cannam@167: @ctindex FFTW_REDFT00 cannam@167: cannam@167: @item cannam@167: @code{FFTW_REDFT10} (DCT-II, ``the'' DCT): even around @math{j=-0.5} and even around @math{j=n-0.5}. cannam@167: @ctindex FFTW_REDFT10 cannam@167: cannam@167: @item cannam@167: @code{FFTW_REDFT01} (DCT-III, ``the'' IDCT): even around @math{j=0} and odd around @math{j=n}. cannam@167: @ctindex FFTW_REDFT01 cannam@167: @cindex IDCT cannam@167: cannam@167: @item cannam@167: @code{FFTW_REDFT11} (DCT-IV): even around @math{j=-0.5} and odd around @math{j=n-0.5}. cannam@167: @ctindex FFTW_REDFT11 cannam@167: cannam@167: @item cannam@167: @code{FFTW_RODFT00} (DST-I): odd around @math{j=-1} and odd around @math{j=n}. cannam@167: @ctindex FFTW_RODFT00 cannam@167: cannam@167: @item cannam@167: @code{FFTW_RODFT10} (DST-II): odd around @math{j=-0.5} and odd around @math{j=n-0.5}. cannam@167: @ctindex FFTW_RODFT10 cannam@167: cannam@167: @item cannam@167: @code{FFTW_RODFT01} (DST-III): odd around @math{j=-1} and even around @math{j=n-1}. cannam@167: @ctindex FFTW_RODFT01 cannam@167: cannam@167: @item cannam@167: @code{FFTW_RODFT11} (DST-IV): odd around @math{j=-0.5} and even around @math{j=n-0.5}. cannam@167: @ctindex FFTW_RODFT11 cannam@167: cannam@167: @end itemize cannam@167: cannam@167: Note that these symmetries apply to the ``logical'' array being cannam@167: transformed; @strong{there are no constraints on your physical input cannam@167: data}. So, for example, if you specify a size-5 REDFT00 (DCT-I) of the cannam@167: data @math{abcde}, it corresponds to the DFT of the logical even array cannam@167: @math{abcdedcb} of size 8. A size-4 REDFT10 (DCT-II) of the data cannam@167: @math{abcd} corresponds to the size-8 logical DFT of the even array cannam@167: @math{abcddcba}, shifted by half a sample. cannam@167: cannam@167: All of these transforms are invertible. The inverse of R*DFT00 is cannam@167: R*DFT00; of R*DFT10 is R*DFT01 and vice versa (these are often called cannam@167: simply ``the'' DCT and IDCT, respectively); and of R*DFT11 is R*DFT11. cannam@167: However, the transforms computed by FFTW are unnormalized, exactly cannam@167: like the corresponding real and complex DFTs, so computing a transform cannam@167: followed by its inverse yields the original array scaled by @math{N}, cannam@167: where @math{N} is the @emph{logical} DFT size. For REDFT00, cannam@167: @math{N=2(n-1)}; for RODFT00, @math{N=2(n+1)}; otherwise, @math{N=2n}. cannam@167: @cindex normalization cannam@167: @cindex IDCT cannam@167: cannam@167: cannam@167: Note that the boundary conditions of the transform output array are cannam@167: given by the input boundary conditions of the inverse transform. cannam@167: Thus, the above transforms are all inequivalent in terms of cannam@167: input/output boundary conditions, even neglecting the 0.5 shift cannam@167: difference. cannam@167: cannam@167: FFTW is most efficient when @math{N} is a product of small factors; note cannam@167: that this @emph{differs} from the factorization of the physical size cannam@167: @code{n} for REDFT00 and RODFT00! There is another oddity: @code{n=1} cannam@167: REDFT00 transforms correspond to @math{N=0}, and so are @emph{not cannam@167: defined} (the planner will return @code{NULL}). Otherwise, any positive cannam@167: @code{n} is supported. cannam@167: cannam@167: For the precise mathematical definitions of these transforms as used by cannam@167: FFTW, see @ref{What FFTW Really Computes}. (For people accustomed to cannam@167: the DCT/DST, FFTW's definitions have a coefficient of @math{2} in front cannam@167: of the cos/sin functions so that they correspond precisely to an cannam@167: even/odd DFT of size @math{N}. Some authors also include additional cannam@167: multiplicative factors of cannam@167: @ifinfo cannam@167: sqrt(2) cannam@167: @end ifinfo cannam@167: @html cannam@167: √2 cannam@167: @end html cannam@167: @tex cannam@167: $\sqrt{2}$ cannam@167: @end tex cannam@167: for selected inputs and outputs; this makes cannam@167: the transform orthogonal, but sacrifices the direct equivalence to a cannam@167: symmetric DFT.) cannam@167: cannam@167: @subsubheading Which type do you need? cannam@167: cannam@167: Since the required flavor of even/odd DFT depends upon your problem, cannam@167: you are the best judge of this choice, but we can make a few comments cannam@167: on relative efficiency to help you in your selection. In particular, cannam@167: R*DFT01 and R*DFT10 tend to be slightly faster than R*DFT11 cannam@167: (especially for odd sizes), while the R*DFT00 transforms are sometimes cannam@167: significantly slower (especially for even sizes).@footnote{R*DFT00 is cannam@167: sometimes slower in FFTW because we discovered that the standard cannam@167: algorithm for computing this by a pre/post-processed real DFT---the cannam@167: algorithm used in FFTPACK, Numerical Recipes, and other sources for cannam@167: decades now---has serious numerical problems: it already loses several cannam@167: decimal places of accuracy for 16k sizes. There seem to be only two cannam@167: alternatives in the literature that do not suffer similarly: a cannam@167: recursive decomposition into smaller DCTs, which would require a large cannam@167: set of codelets for efficiency and generality, or sacrificing a factor of cannam@167: @tex cannam@167: $\sim 2$ cannam@167: @end tex cannam@167: @ifnottex cannam@167: 2 cannam@167: @end ifnottex cannam@167: in speed to use a real DFT of twice the size. We currently cannam@167: employ the latter technique for general @math{n}, as well as a limited cannam@167: form of the former method: a split-radix decomposition when @math{n} cannam@167: is odd (@math{N} a multiple of 4). For @math{N} containing many cannam@167: factors of 2, the split-radix method seems to recover most of the cannam@167: speed of the standard algorithm without the accuracy tradeoff.} cannam@167: cannam@167: Thus, if only the boundary conditions on the transform inputs are cannam@167: specified, we generally recommend R*DFT10 over R*DFT00 and R*DFT01 over cannam@167: R*DFT11 (unless the half-sample shift or the self-inverse property is cannam@167: significant for your problem). cannam@167: cannam@167: If performance is important to you and you are using only small sizes cannam@167: (say @math{n<200}), e.g. for multi-dimensional transforms, then you cannam@167: might consider generating hard-coded transforms of those sizes and types cannam@167: that you are interested in (@pxref{Generating your own code}). cannam@167: cannam@167: We are interested in hearing what types of symmetric transforms you find cannam@167: most useful. cannam@167: cannam@167: @c =========> cannam@167: @node The Discrete Hartley Transform, , Real even/odd DFTs (cosine/sine transforms), More DFTs of Real Data cannam@167: @subsection The Discrete Hartley Transform cannam@167: cannam@167: If you are planning to use the DHT because you've heard that it is cannam@167: ``faster'' than the DFT (FFT), @strong{stop here}. The DHT is not cannam@167: faster than the DFT. That story is an old but enduring misconception cannam@167: that was debunked in 1987. cannam@167: cannam@167: The discrete Hartley transform (DHT) is an invertible linear transform cannam@167: closely related to the DFT. In the DFT, one multiplies each input by cannam@167: @math{cos - i * sin} (a complex exponential), whereas in the DHT each cannam@167: input is multiplied by simply @math{cos + sin}. Thus, the DHT cannam@167: transforms @code{n} real numbers to @code{n} real numbers, and has the cannam@167: convenient property of being its own inverse. In FFTW, a DHT (of any cannam@167: positive @code{n}) can be specified by an r2r kind of @code{FFTW_DHT}. cannam@167: @ctindex FFTW_DHT cannam@167: @cindex discrete Hartley transform cannam@167: @cindex DHT cannam@167: cannam@167: Like the DFT, in FFTW the DHT is unnormalized, so computing a DHT of cannam@167: size @code{n} followed by another DHT of the same size will result in cannam@167: the original array multiplied by @code{n}. cannam@167: @cindex normalization cannam@167: cannam@167: The DHT was originally proposed as a more efficient alternative to the cannam@167: DFT for real data, but it was subsequently shown that a specialized DFT cannam@167: (such as FFTW's r2hc or r2c transforms) could be just as fast. In FFTW, cannam@167: the DHT is actually computed by post-processing an r2hc transform, so cannam@167: there is ordinarily no reason to prefer it from a performance cannam@167: perspective.@footnote{We provide the DHT mainly as a byproduct of some cannam@167: internal algorithms. FFTW computes a real input/output DFT of cannam@167: @emph{prime} size by re-expressing it as a DHT plus post/pre-processing cannam@167: and then using Rader's prime-DFT algorithm adapted to the DHT.} cannam@167: However, we have heard rumors that the DHT might be the most appropriate cannam@167: transform in its own right for certain applications, and we would be cannam@167: very interested to hear from anyone who finds it useful. cannam@167: cannam@167: If @code{FFTW_DHT} is specified for multiple dimensions of a cannam@167: multi-dimensional transform, FFTW computes the separable product of 1d cannam@167: DHTs along each dimension. Unfortunately, this is not quite the same cannam@167: thing as a true multi-dimensional DHT; you can compute the latter, if cannam@167: necessary, with at most @code{rank-1} post-processing passes cannam@167: [see e.g. H. Hao and R. N. Bracewell, @i{Proc. IEEE} @b{75}, 264--266 (1987)]. cannam@167: cannam@167: For the precise mathematical definition of the DHT as used by FFTW, see cannam@167: @ref{What FFTW Really Computes}. cannam@167: