Mercurial > hg > sv-dependency-builds

comparison src/fftw-3.3.8/doc/html/Multi_002dDimensional-DFTs-of-Real-Data.html @ 82:d0c2a83c1364

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add FFTW 3.3.8 source, and a Linux build
author Chris Cannam
date Tue, 19 Nov 2019 14:52:55 +0000
parents
children
comparison
equal deleted inserted replaced
81:7029a4916348 82:d0c2a83c1364
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.8, 24 May 2018).
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 6.3, http://www.gnu.org/software/texinfo/ -->
24 <head>
25 <title>FFTW 3.3.8: Multi-Dimensional DFTs of Real Data</title>
26
27 <meta name="description" content="FFTW 3.3.8: Multi-Dimensional DFTs of Real Data">
28 <meta name="keywords" content="FFTW 3.3.8: Multi-Dimensional 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="More-DFTs-of-Real-Data.html#More-DFTs-of-Real-Data" rel="next" title="More DFTs of Real Data">
38 <link href="One_002dDimensional-DFTs-of-Real-Data.html#One_002dDimensional-DFTs-of-Real-Data" rel="prev" title="One-Dimensional DFTs of Real Data">
39 <style type="text/css">
40 <!--
41 a.summary-letter {text-decoration: none}
42 blockquote.indentedblock {margin-right: 0em}
43 blockquote.smallindentedblock {margin-right: 0em; font-size: smaller}
44 blockquote.smallquotation {font-size: smaller}
45 div.display {margin-left: 3.2em}
46 div.example {margin-left: 3.2em}
47 div.lisp {margin-left: 3.2em}
48 div.smalldisplay {margin-left: 3.2em}
49 div.smallexample {margin-left: 3.2em}
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.nolinebreak {white-space: nowrap}
61 span.roman {font-family: initial; font-weight: normal}
62 span.sansserif {font-family: sans-serif; font-weight: normal}
63 ul.no-bullet {list-style: none}
64 -->
65 </style>
66
67
68 </head>
69
70 <body lang="en">
71 <a name="Multi_002dDimensional-DFTs-of-Real-Data"></a>
72 <div class="header">
73 <p>
74 Next: <a href="More-DFTs-of-Real-Data.html#More-DFTs-of-Real-Data" accesskey="n" rel="next">More DFTs of Real Data</a>, Previous: <a href="One_002dDimensional-DFTs-of-Real-Data.html#One_002dDimensional-DFTs-of-Real-Data" accesskey="p" rel="prev">One-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>
75 </div>
76 <hr>
77 <a name="Multi_002dDimensional-DFTs-of-Real-Data-1"></a>
78 <h3 class="section">2.4 Multi-Dimensional DFTs of Real Data</h3>
79
80 <p>Multi-dimensional DFTs of real data use the following planner routines:
81 </p>
82 <div class="example">
83 <pre class="example">fftw_plan fftw_plan_dft_r2c_2d(int n0, int n1,
84 double *in, fftw_complex *out,
85 unsigned flags);
86 fftw_plan fftw_plan_dft_r2c_3d(int n0, int n1, int n2,
87 double *in, fftw_complex *out,
88 unsigned flags);
89 fftw_plan fftw_plan_dft_r2c(int rank, const int *n,
90 double *in, fftw_complex *out,
91 unsigned flags);
92 </pre></div>
93 <a name="index-fftw_005fplan_005fdft_005fr2c_005f2d"></a>
94 <a name="index-fftw_005fplan_005fdft_005fr2c_005f3d"></a>
95 <a name="index-fftw_005fplan_005fdft_005fr2c"></a>
96
97 <p>as well as the corresponding <code>c2r</code> routines with the input/output
98 types swapped. These routines work similarly to their complex
99 analogues, except for the fact that here the complex output array is cut
100 roughly in half and the real array requires padding for in-place
101 transforms (as in 1d, above).
102 </p>
103 <p>As before, <code>n</code> is the logical size of the array, and the
104 consequences of this on the the format of the complex arrays deserve
105 careful attention.
106 <a name="index-r2c_002fc2r-multi_002ddimensional-array-format"></a>
107 Suppose that the real data has dimensions n<sub>0</sub>&nbsp;&times;&nbsp;n<sub>1</sub>&nbsp;&times;&nbsp;n<sub>2</sub>&nbsp;&times;&nbsp;&hellip;&nbsp;&times;&nbsp;n<sub>d-1</sub>
108 (in row-major order).
109 Then, after an r2c transform, the output is an n<sub>0</sub>&nbsp;&times;&nbsp;n<sub>1</sub>&nbsp;&times;&nbsp;n<sub>2</sub>&nbsp;&times;&nbsp;&hellip;&nbsp;&times;&nbsp;(n<sub>d-1</sub>/2 + 1)
110 array of
111 <code>fftw_complex</code> values in row-major order, corresponding to slightly
112 over half of the output of the corresponding complex DFT. (The division
113 is rounded down.) The ordering of the data is otherwise exactly the
114 same as in the complex-DFT case.
115 </p>
116 <p>For out-of-place transforms, this is the end of the story: the real
117 data is stored as a row-major array of size n<sub>0</sub>&nbsp;&times;&nbsp;n<sub>1</sub>&nbsp;&times;&nbsp;n<sub>2</sub>&nbsp;&times;&nbsp;&hellip;&nbsp;&times;&nbsp;n<sub>d-1</sub>
118 and the complex
119 data is stored as a row-major array of size n<sub>0</sub>&nbsp;&times;&nbsp;n<sub>1</sub>&nbsp;&times;&nbsp;n<sub>2</sub>&nbsp;&times;&nbsp;&hellip;&nbsp;&times;&nbsp;(n<sub>d-1</sub>/2 + 1)
120 .
121 </p>
122 <p>For in-place transforms, however, extra padding of the real-data array
123 is necessary because the complex array is larger than the real array,
124 and the two arrays share the same memory locations. Thus, for
125 in-place transforms, the final dimension of the real-data array must
126 be padded with extra values to accommodate the size of the complex
127 data&mdash;two values if the last dimension is even and one if it is odd.
128 <a name="index-padding-1"></a>
129 That is, the last dimension of the real data must physically contain
130 2 * (n<sub>d-1</sub>/2+1)
131 <code>double</code> values (exactly enough to hold the complex data).
132 This physical array size does not, however, change the <em>logical</em>
133 array size&mdash;only
134 n<sub>d-1</sub>
135 values are actually stored in the last dimension, and
136 n<sub>d-1</sub>
137 is the last dimension passed to the plan-creation routine.
138 </p>
139 <p>For example, consider the transform of a two-dimensional real array of
140 size <code>n0</code> by <code>n1</code>. The output of the r2c transform is a
141 two-dimensional complex array of size <code>n0</code> by <code>n1/2+1</code>, where
142 the <code>y</code> dimension has been cut nearly in half because of
143 redundancies in the output. Because <code>fftw_complex</code> is twice the
144 size of <code>double</code>, the output array is slightly bigger than the
145 input array. Thus, if we want to compute the transform in place, we
146 must <em>pad</em> the input array so that it is of size <code>n0</code> by
147 <code>2*(n1/2+1)</code>. If <code>n1</code> is even, then there are two padding
148 elements at the end of each row (which need not be initialized, as they
149 are only used for output).
150 </p>
151 <p>The following illustration depicts the input and output arrays just
152 described, for both the out-of-place and in-place transforms (with the
153 arrows indicating consecutive memory locations):
154 <img src="rfftwnd-for-html.png" alt="rfftwnd-for-html">
155 </p>
156 <p>These transforms are unnormalized, so an r2c followed by a c2r
157 transform (or vice versa) will result in the original data scaled by
158 the number of real data elements&mdash;that is, the product of the
159 (logical) dimensions of the real data.
160 <a name="index-normalization-1"></a>
161 </p>
162
163 <p>(Because the last dimension is treated specially, if it is equal to
164 <code>1</code> the transform is <em>not</em> equivalent to a lower-dimensional
165 r2c/c2r transform. In that case, the last complex dimension also has
166 size <code>1</code> (<code>=1/2+1</code>), and no advantage is gained over the
167 complex transforms.)
168 </p>
169 <hr>
170 <div class="header">
171 <p>
172 Next: <a href="More-DFTs-of-Real-Data.html#More-DFTs-of-Real-Data" accesskey="n" rel="next">More DFTs of Real Data</a>, Previous: <a href="One_002dDimensional-DFTs-of-Real-Data.html#One_002dDimensional-DFTs-of-Real-Data" accesskey="p" rel="prev">One-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>
173 </div>
174
175
176
177 </body>
178 </html>