Mercurial > hg > sv-dependency-builds

comparison src/fftw-3.3.5/doc/html/More-DFTs-of-Real-Data.html @ 42:2cd0e3b3e1fd

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Current fftw source
author Chris Cannam
date Tue, 18 Oct 2016 13:40:26 +0100
parents
children
comparison
equal deleted inserted replaced
41:481f5f8c5634 42:2cd0e3b3e1fd
1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
2 <html>
3 <!-- This manual is for FFTW
4 (version 3.3.5, 30 July 2016).
5
6 Copyright (C) 2003 Matteo Frigo.
7
8 Copyright (C) 2003 Massachusetts Institute of Technology.
9
10 Permission is granted to make and distribute verbatim copies of this
11 manual provided the copyright notice and this permission notice are
12 preserved on all copies.
13
14 Permission is granted to copy and distribute modified versions of this
15 manual under the conditions for verbatim copying, provided that the
16 entire resulting derived work is distributed under the terms of a
17 permission notice identical to this one.
18
19 Permission is granted to copy and distribute translations of this manual
20 into another language, under the above conditions for modified versions,
21 except that this permission notice may be stated in a translation
22 approved by the Free Software Foundation. -->
23 <!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
24 <head>
25 <title>FFTW 3.3.5: More DFTs of Real Data</title>
26
27 <meta name="description" content="FFTW 3.3.5: More DFTs of Real Data">
28 <meta name="keywords" content="FFTW 3.3.5: More DFTs of Real Data">
29 <meta name="resource-type" content="document">
30 <meta name="distribution" content="global">
31 <meta name="Generator" content="makeinfo">
32 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
33 <link href="index.html#Top" rel="start" title="Top">
34 <link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index">
35 <link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
36 <link href="Tutorial.html#Tutorial" rel="up" title="Tutorial">
37 <link href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT" rel="next" title="The Halfcomplex-format DFT">
38 <link href="Multi_002dDimensional-DFTs-of-Real-Data.html#Multi_002dDimensional-DFTs-of-Real-Data" rel="prev" title="Multi-Dimensional DFTs of Real Data">
39 <style type="text/css">
40 <!--
41 a.summary-letter {text-decoration: none}
42 blockquote.smallquotation {font-size: smaller}
43 div.display {margin-left: 3.2em}
44 div.example {margin-left: 3.2em}
45 div.indentedblock {margin-left: 3.2em}
46 div.lisp {margin-left: 3.2em}
47 div.smalldisplay {margin-left: 3.2em}
48 div.smallexample {margin-left: 3.2em}
49 div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
50 div.smalllisp {margin-left: 3.2em}
51 kbd {font-style:oblique}
52 pre.display {font-family: inherit}
53 pre.format {font-family: inherit}
54 pre.menu-comment {font-family: serif}
55 pre.menu-preformatted {font-family: serif}
56 pre.smalldisplay {font-family: inherit; font-size: smaller}
57 pre.smallexample {font-size: smaller}
58 pre.smallformat {font-family: inherit; font-size: smaller}
59 pre.smalllisp {font-size: smaller}
60 span.nocodebreak {white-space:nowrap}
61 span.nolinebreak {white-space:nowrap}
62 span.roman {font-family:serif; font-weight:normal}
63 span.sansserif {font-family:sans-serif; font-weight:normal}
64 ul.no-bullet {list-style: none}
65 -->
66 </style>
67
68
69 </head>
70
71 <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
72 <a name="More-DFTs-of-Real-Data"></a>
73 <div class="header">
74 <p>
75 Previous: <a href="Multi_002dDimensional-DFTs-of-Real-Data.html#Multi_002dDimensional-DFTs-of-Real-Data" accesskey="p" rel="prev">Multi-Dimensional DFTs of Real Data</a>, Up: <a href="Tutorial.html#Tutorial" accesskey="u" rel="up">Tutorial</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
76 </div>
77 <hr>
78 <a name="More-DFTs-of-Real-Data-1"></a>
79 <h3 class="section">2.5 More DFTs of Real Data</h3>
80 <table class="menu" border="0" cellspacing="0">
81 <tr><td align="left" valign="top">&bull; <a href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT" accesskey="1">The Halfcomplex-format DFT</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">
82 </td></tr>
83 <tr><td align="left" valign="top">&bull; <a href="Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029.html#Real-even_002fodd-DFTs-_0028cosine_002fsine-transforms_0029" accesskey="2">Real even/odd DFTs (cosine/sine transforms)</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">
84 </td></tr>
85 <tr><td align="left" valign="top">&bull; <a href="The-Discrete-Hartley-Transform.html#The-Discrete-Hartley-Transform" accesskey="3">The Discrete Hartley Transform</a>:</td><td>&nbsp;&nbsp;</td><td align="left" valign="top">
86 </td></tr>
87 </table>
88
89 <p>FFTW supports several other transform types via a unified <em>r2r</em>
90 (real-to-real) interface,
91 <a name="index-r2r"></a>
92 so called because it takes a real (<code>double</code>) array and outputs a
93 real array of the same size. These r2r transforms currently fall into
94 three categories: DFTs of real input and complex-Hermitian output in
95 halfcomplex format, DFTs of real input with even/odd symmetry
96 (a.k.a. discrete cosine/sine transforms, DCTs/DSTs), and discrete
97 Hartley transforms (DHTs), all described in more detail by the
98 following sections.
99 </p>
100 <p>The r2r transforms follow the by now familiar interface of creating an
101 <code>fftw_plan</code>, executing it with <code>fftw_execute(plan)</code>, and
102 destroying it with <code>fftw_destroy_plan(plan)</code>. Furthermore, all
103 r2r transforms share the same planner interface:
104 </p>
105 <div class="example">
106 <pre class="example">fftw_plan fftw_plan_r2r_1d(int n, double *in, double *out,
107 fftw_r2r_kind kind, unsigned flags);
108 fftw_plan fftw_plan_r2r_2d(int n0, int n1, double *in, double *out,
109 fftw_r2r_kind kind0, fftw_r2r_kind kind1,
110 unsigned flags);
111 fftw_plan fftw_plan_r2r_3d(int n0, int n1, int n2,
112 double *in, double *out,
113 fftw_r2r_kind kind0,
114 fftw_r2r_kind kind1,
115 fftw_r2r_kind kind2,
116 unsigned flags);
117 fftw_plan fftw_plan_r2r(int rank, const int *n, double *in, double *out,
118 const fftw_r2r_kind *kind, unsigned flags);
119 </pre></div>
120 <a name="index-fftw_005fplan_005fr2r_005f1d"></a>
121 <a name="index-fftw_005fplan_005fr2r_005f2d"></a>
122 <a name="index-fftw_005fplan_005fr2r_005f3d"></a>
123 <a name="index-fftw_005fplan_005fr2r"></a>
124
125 <p>Just as for the complex DFT, these plan 1d/2d/3d/multi-dimensional
126 transforms for contiguous arrays in row-major order, transforming (real)
127 input to output of the same size, where <code>n</code> specifies the
128 <em>physical</em> dimensions of the arrays. All positive <code>n</code> are
129 supported (with the exception of <code>n=1</code> for the <code>FFTW_REDFT00</code>
130 kind, noted in the real-even subsection below); products of small
131 factors are most efficient (factorizing <code>n-1</code> and <code>n+1</code> for
132 <code>FFTW_REDFT00</code> and <code>FFTW_RODFT00</code> kinds, described below), but
133 an <i>O</i>(<i>n</i>&nbsp;log&nbsp;<i>n</i>) algorithm is used even for prime sizes.
134 </p>
135 <p>Each dimension has a <em>kind</em> parameter, of type
136 <code>fftw_r2r_kind</code>, specifying the kind of r2r transform to be used
137 for that dimension.
138 <a name="index-kind-_0028r2r_0029"></a>
139 <a name="index-fftw_005fr2r_005fkind"></a>
140 (In the case of <code>fftw_plan_r2r</code>, this is an array <code>kind[rank]</code>
141 where <code>kind[i]</code> is the transform kind for the dimension
142 <code>n[i]</code>.) The kind can be one of a set of predefined constants,
143 defined in the following subsections.
144 </p>
145 <p>In other words, FFTW computes the separable product of the specified
146 r2r transforms over each dimension, which can be used e.g. for partial
147 differential equations with mixed boundary conditions. (For some r2r
148 kinds, notably the halfcomplex DFT and the DHT, such a separable
149 product is somewhat problematic in more than one dimension, however,
150 as is described below.)
151 </p>
152 <p>In the current version of FFTW, all r2r transforms except for the
153 halfcomplex type are computed via pre- or post-processing of
154 halfcomplex transforms, and they are therefore not as fast as they
155 could be. Since most other general DCT/DST codes employ a similar
156 algorithm, however, FFTW&rsquo;s implementation should provide at least
157 competitive performance.
158 </p>
159 <hr>
160 <div class="header">
161 <p>
162 Previous: <a href="Multi_002dDimensional-DFTs-of-Real-Data.html#Multi_002dDimensional-DFTs-of-Real-Data" accesskey="p" rel="prev">Multi-Dimensional DFTs of Real Data</a>, Up: <a href="Tutorial.html#Tutorial" accesskey="u" rel="up">Tutorial</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
163 </div>
164
165
166
167 </body>
168 </html>