Mercurial > hg > sv-dependency-builds

comparison src/fftw-3.3.8/doc/html/Real_002ddata-DFT-Array-Format.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: Real-data DFT Array Format</title>
26
27 <meta name="description" content="FFTW 3.3.8: Real-data DFT Array Format">
28 <meta name="keywords" content="FFTW 3.3.8: Real-data DFT Array Format">
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="Basic-Interface.html#Basic-Interface" rel="up" title="Basic Interface">
37 <link href="Real_002dto_002dReal-Transforms.html#Real_002dto_002dReal-Transforms" rel="next" title="Real-to-Real Transforms">
38 <link href="Real_002ddata-DFTs.html#Real_002ddata-DFTs" rel="prev" title="Real-data DFTs">
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="Real_002ddata-DFT-Array-Format"></a>
72 <div class="header">
73 <p>
74 Next: <a href="Real_002dto_002dReal-Transforms.html#Real_002dto_002dReal-Transforms" accesskey="n" rel="next">Real-to-Real Transforms</a>, Previous: <a href="Real_002ddata-DFTs.html#Real_002ddata-DFTs" accesskey="p" rel="prev">Real-data DFTs</a>, Up: <a href="Basic-Interface.html#Basic-Interface" accesskey="u" rel="up">Basic Interface</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="Real_002ddata-DFT-Array-Format-1"></a>
78 <h4 class="subsection">4.3.4 Real-data DFT Array Format</h4>
79 <a name="index-r2c_002fc2r-multi_002ddimensional-array-format-1"></a>
80
81 <p>The output of a DFT of real data (r2c) contains symmetries that, in
82 principle, make half of the outputs redundant (see <a href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes">What FFTW Really Computes</a>). (Similarly for the input of an inverse c2r transform.) In
83 practice, it is not possible to entirely realize these savings in an
84 efficient and understandable format that generalizes to
85 multi-dimensional transforms. Instead, the output of the r2c
86 transforms is <em>slightly</em> over half of the output of the
87 corresponding complex transform. We do not &ldquo;pack&rdquo; the data in any
88 way, but store it as an ordinary array of <code>fftw_complex</code> values.
89 In fact, this data is simply a subsection of what would be the array in
90 the corresponding complex transform.
91 </p>
92 <p>Specifically, for a real transform of <em>d</em> (= <code>rank</code>)
93 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>
94 , the complex data 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)
95 array of
96 <code>fftw_complex</code> values in row-major order (with the division rounded
97 down). That is, we only store the <em>lower</em> half (non-negative
98 frequencies), plus one element, of the last dimension of the data from
99 the ordinary complex transform. (We could have instead taken half of
100 any other dimension, but implementation turns out to be simpler if the
101 last, contiguous, dimension is used.)
102 </p>
103 <a name="index-out_002dof_002dplace-1"></a>
104 <p>For an out-of-place transform, the real data is simply an array with
105 physical 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>
106 in row-major order.
107 </p>
108 <a name="index-in_002dplace-4"></a>
109 <a name="index-padding-3"></a>
110 <p>For an in-place transform, some complications arise since the complex data
111 is slightly larger than the real data. In this case, the final
112 dimension of the real data must be <em>padded</em> with extra values to
113 accommodate the size of the complex data&mdash;two extra if the last
114 dimension is even and one if it is odd. That is, the last dimension of
115 the real data must physically contain
116 2 * (n<sub>d-1</sub>/2+1)
117 <code>double</code> values (exactly enough to hold the complex data). This
118 physical array size does not, however, change the <em>logical</em> array
119 size&mdash;only
120 n<sub>d-1</sub>
121 values are actually stored in the last dimension, and
122 n<sub>d-1</sub>
123 is the last dimension passed to the planner.
124 </p>
125 <hr>
126 <div class="header">
127 <p>
128 Next: <a href="Real_002dto_002dReal-Transforms.html#Real_002dto_002dReal-Transforms" accesskey="n" rel="next">Real-to-Real Transforms</a>, Previous: <a href="Real_002ddata-DFTs.html#Real_002ddata-DFTs" accesskey="p" rel="prev">Real-data DFTs</a>, Up: <a href="Basic-Interface.html#Basic-Interface" accesskey="u" rel="up">Basic Interface</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>
129 </div>
130
131
132
133 </body>
134 </html>