3
<title>More DFTs of Real Data - FFTW 3.1.2</title>
4
<meta http-equiv="Content-Type" content="text/html">
5
<meta name="description" content="FFTW 3.1.2">
6
<meta name="generator" content="makeinfo 4.8">
7
<link title="Top" rel="start" href="index.html#Top">
8
<link rel="up" href="Tutorial.html#Tutorial" title="Tutorial">
9
<link rel="prev" href="Multi_002dDimensional-DFTs-of-Real-Data.html#Multi_002dDimensional-DFTs-of-Real-Data" title="Multi-Dimensional DFTs of Real Data">
10
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
12
This manual is for FFTW
13
(version 3.1.2, 23 June 2006).
15
Copyright (C) 2003 Matteo Frigo.
17
Copyright (C) 2003 Massachusetts Institute of Technology.
19
Permission is granted to make and distribute verbatim copies of
20
this manual provided the copyright notice and this permission
21
notice are preserved on all copies.
23
Permission is granted to copy and distribute modified versions of
24
this manual under the conditions for verbatim copying, provided
25
that the entire resulting derived work is distributed under the
26
terms of a permission notice identical to this one.
28
Permission is granted to copy and distribute translations of this
29
manual into another language, under the above conditions for
30
modified versions, except that this permission notice may be
31
stated in a translation approved by the Free Software Foundation.
33
<meta http-equiv="Content-Style-Type" content="text/css">
34
<style type="text/css"><!--
35
pre.display { font-family:inherit }
36
pre.format { font-family:inherit }
37
pre.smalldisplay { font-family:inherit; font-size:smaller }
38
pre.smallformat { font-family:inherit; font-size:smaller }
39
pre.smallexample { font-size:smaller }
40
pre.smalllisp { font-size:smaller }
41
span.sc { font-variant:small-caps }
42
span.roman { font-family:serif; font-weight:normal; }
43
span.sansserif { font-family:sans-serif; font-weight:normal; }
49
<a name="More-DFTs-of-Real-Data"></a>
50
Previous: <a rel="previous" accesskey="p" href="Multi_002dDimensional-DFTs-of-Real-Data.html#Multi_002dDimensional-DFTs-of-Real-Data">Multi-Dimensional DFTs of Real Data</a>,
51
Up: <a rel="up" accesskey="u" href="Tutorial.html#Tutorial">Tutorial</a>
55
<h3 class="section">2.5 More DFTs of Real Data</h3>
58
<li><a accesskey="1" href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT">The Halfcomplex-format DFT</a>
59
<li><a accesskey="2" href="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html#Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029">Real even/odd DFTs (cosine/sine transforms)</a>
60
<li><a accesskey="3" href="The-Discrete-Hartley-Transform.html#The-Discrete-Hartley-Transform">The Discrete Hartley Transform</a>
63
<p>FFTW supports several other transform types via a unified <dfn>r2r</dfn>
64
(real-to-real) interface,
65
<a name="index-r2r-64"></a>so called because it takes a real (<code>double</code>) array and outputs a
66
real array of the same size. These r2r transforms currently fall into
67
three categories: DFTs of real input and complex-Hermitian output in
68
halfcomplex format, DFTs of real input with even/odd symmetry
69
(a.k.a. discrete cosine/sine transforms, DCTs/DSTs), and discrete
70
Hartley transforms (DHTs), all described in more detail by the
73
<p>The r2r transforms follow the by now familiar interface of creating an
74
<code>fftw_plan</code>, executing it with <code>fftw_execute(plan)</code>, and
75
destroying it with <code>fftw_destroy_plan(plan)</code>. Furthermore, all
76
r2r transforms share the same planner interface:
78
<pre class="example"> fftw_plan fftw_plan_r2r_1d(int n, double *in, double *out,
79
fftw_r2r_kind kind, unsigned flags);
80
fftw_plan fftw_plan_r2r_2d(int nx, int ny, double *in, double *out,
81
fftw_r2r_kind kindx, fftw_r2r_kind kindy,
83
fftw_plan fftw_plan_r2r_3d(int nx, int ny, int nz,
84
double *in, double *out,
89
fftw_plan fftw_plan_r2r(int rank, const int *n, double *in, double *out,
90
const fftw_r2r_kind *kind, unsigned flags);
92
<p><a name="index-fftw_005fplan_005fr2r_005f1d-65"></a><a name="index-fftw_005fplan_005fr2r_005f2d-66"></a><a name="index-fftw_005fplan_005fr2r_005f3d-67"></a><a name="index-fftw_005fplan_005fr2r-68"></a>
93
Just as for the complex DFT, these plan 1d/2d/3d/multi-dimensional
94
transforms for contiguous arrays in row-major order, transforming (real)
95
input to output of the same size, where <code>n</code> specifies the
96
<em>physical</em> dimensions of the arrays. All positive <code>n</code> are
97
supported (with the exception of <code>n=1</code> for the <code>FFTW_REDFT00</code>
98
kind, noted in the real-even subsection below); products of small
99
factors are most efficient (factorizing <code>n-1</code> and <code>n+1</code> for
100
<code>FFTW_REDFT00</code> and <code>FFTW_RODFT00</code> kinds, described below), but
101
an <i>O</i>(<i>n</i> log <i>n</i>) algorithm is used even for prime sizes.
103
<p>Each dimension has a <dfn>kind</dfn> parameter, of type
104
<code>fftw_r2r_kind</code>, specifying the kind of r2r transform to be used
106
<a name="index-kind-_0028r2r_0029-69"></a><a name="index-fftw_005fr2r_005fkind-70"></a>(In the case of <code>fftw_plan_r2r</code>, this is an array <code>kind[rank]</code>
107
where <code>kind[i]</code> is the transform kind for the dimension
108
<code>n[i]</code>.) The kind can be one of a set of predefined constants,
109
defined in the following subsections.
111
<p>In other words, FFTW computes the separable product of the specified
112
r2r transforms over each dimension, which can be used e.g. for partial
113
differential equations with mixed boundary conditions. (For some r2r
114
kinds, notably the halfcomplex DFT and the DHT, such a separable
115
product is somewhat problematic in more than one dimension, however,
116
as is described below.)
118
<p>In the current version of FFTW, all r2r transforms except for the
119
halfcomplex type are computed via pre- or post-processing of
120
halfcomplex transforms, and they are therefore not as fast as they
121
could be. Since most other general DCT/DST codes employ a similar
122
algorithm, however, FFTW's implementation should provide at least
123
competitive performance.