Mercurial > hg > sv-dependency-builds

comparison src/fftw-3.3.5/doc/html/Multi_002ddimensional-Transforms.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: Multi-dimensional Transforms</title>
26
27 <meta name="description" content="FFTW 3.3.5: Multi-dimensional Transforms">
28 <meta name="keywords" content="FFTW 3.3.5: Multi-dimensional Transforms">
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="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes" rel="up" title="What FFTW Really Computes">
37 <link href="Multi_002dthreaded-FFTW.html#Multi_002dthreaded-FFTW" rel="next" title="Multi-threaded FFTW">
38 <link href="1d-Discrete-Hartley-Transforms-_0028DHTs_0029.html#g_t1d-Discrete-Hartley-Transforms-_0028DHTs_0029" rel="prev" title="1d Discrete Hartley Transforms (DHTs)">
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="Multi_002ddimensional-Transforms"></a>
73 <div class="header">
74 <p>
75 Previous: <a href="1d-Discrete-Hartley-Transforms-_0028DHTs_0029.html#g_t1d-Discrete-Hartley-Transforms-_0028DHTs_0029" accesskey="p" rel="prev">1d Discrete Hartley Transforms (DHTs)</a>, Up: <a href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes" accesskey="u" rel="up">What FFTW Really Computes</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="Multi_002ddimensional-Transforms-1"></a>
79 <h4 class="subsection">4.8.6 Multi-dimensional Transforms</h4>
80
81 <p>The multi-dimensional transforms of FFTW, in general, compute simply the
82 separable product of the given 1d transform along each dimension of the
83 array. Since each of these transforms is unnormalized, computing the
84 forward followed by the backward/inverse multi-dimensional transform
85 will result in the original array scaled by the product of the
86 normalization factors for each dimension (e.g. the product of the
87 dimension sizes, for a multi-dimensional DFT).
88 </p>
89
90 <a name="index-r2c-3"></a>
91 <p>The definition of FFTW&rsquo;s multi-dimensional DFT of real data (r2c)
92 deserves special attention. In this case, we logically compute the full
93 multi-dimensional DFT of the input data; since the input data are purely
94 real, the output data have the Hermitian symmetry and therefore only one
95 non-redundant half need be stored. More specifically, for 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> multi-dimensional real-input DFT, the full (logical) complex output array
96 <i>Y</i>[<i>k</i><sub>0</sub>, <i>k</i><sub>1</sub>, ...,
97 <i>k</i><sub><i>d-1</i></sub>]has the symmetry:
98 <i>Y</i>[<i>k</i><sub>0</sub>, <i>k</i><sub>1</sub>, ...,
99 <i>k</i><sub><i>d-1</i></sub>] = <i>Y</i>[<i>n</i><sub>0</sub> -
100 <i>k</i><sub>0</sub>, <i>n</i><sub>1</sub> - <i>k</i><sub>1</sub>, ...,
101 <i>n</i><sub><i>d-1</i></sub> - <i>k</i><sub><i>d-1</i></sub>]<sup>*</sup>(where each dimension is periodic). Because of this symmetry, we only
102 store the
103 <i>k</i><sub><i>d-1</i></sub> = 0...<i>n</i><sub><i>d-1</i></sub>/2+1elements of the <em>last</em> dimension (division by <em>2</em> is rounded
104 down). (We could instead have cut any other dimension in half, but the
105 last dimension proved computationally convenient.) This results in the
106 peculiar array format described in more detail by <a href="Real_002ddata-DFT-Array-Format.html#Real_002ddata-DFT-Array-Format">Real-data DFT Array Format</a>.
107 </p>
108 <p>The multi-dimensional c2r transform is simply the unnormalized inverse
109 of the r2c transform. i.e. it is the same as FFTW&rsquo;s complex backward
110 multi-dimensional DFT, operating on a Hermitian input array in the
111 peculiar format mentioned above and outputting a real array (since the
112 DFT output is purely real).
113 </p>
114 <p>We should remind the user that the separable product of 1d transforms
115 along each dimension, as computed by FFTW, is not always the same thing
116 as the usual multi-dimensional transform. A multi-dimensional
117 <code>R2HC</code> (or <code>HC2R</code>) transform is not identical to the
118 multi-dimensional DFT, requiring some post-processing to combine the
119 requisite real and imaginary parts, as was described in <a href="The-Halfcomplex_002dformat-DFT.html#The-Halfcomplex_002dformat-DFT">The Halfcomplex-format DFT</a>. Likewise, FFTW&rsquo;s multidimensional
120 <code>FFTW_DHT</code> r2r transform is not the same thing as the logical
121 multi-dimensional discrete Hartley transform defined in the literature,
122 as discussed in <a href="The-Discrete-Hartley-Transform.html#The-Discrete-Hartley-Transform">The Discrete Hartley Transform</a>.
123 </p>
124 <hr>
125 <div class="header">
126 <p>
127 Previous: <a href="1d-Discrete-Hartley-Transforms-_0028DHTs_0029.html#g_t1d-Discrete-Hartley-Transforms-_0028DHTs_0029" accesskey="p" rel="prev">1d Discrete Hartley Transforms (DHTs)</a>, Up: <a href="What-FFTW-Really-Computes.html#What-FFTW-Really-Computes" accesskey="u" rel="up">What FFTW Really Computes</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>
128 </div>
129
130
131
132 </body>
133 </html>