|
Chris@10
|
1 <html lang="en">
|
|
Chris@10
|
2 <head>
|
|
Chris@10
|
3 <title>Complex Multi-Dimensional DFTs - FFTW 3.3.3</title>
|
|
Chris@10
|
4 <meta http-equiv="Content-Type" content="text/html">
|
|
Chris@10
|
5 <meta name="description" content="FFTW 3.3.3">
|
|
Chris@10
|
6 <meta name="generator" content="makeinfo 4.13">
|
|
Chris@10
|
7 <link title="Top" rel="start" href="index.html#Top">
|
|
Chris@10
|
8 <link rel="up" href="Tutorial.html#Tutorial" title="Tutorial">
|
|
Chris@10
|
9 <link rel="prev" href="Complex-One_002dDimensional-DFTs.html#Complex-One_002dDimensional-DFTs" title="Complex One-Dimensional DFTs">
|
|
Chris@10
|
10 <link rel="next" href="One_002dDimensional-DFTs-of-Real-Data.html#One_002dDimensional-DFTs-of-Real-Data" title="One-Dimensional DFTs of Real Data">
|
|
Chris@10
|
11 <link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
|
|
Chris@10
|
12 <!--
|
|
Chris@10
|
13 This manual is for FFTW
|
|
Chris@10
|
14 (version 3.3.3, 25 November 2012).
|
|
Chris@10
|
15
|
|
Chris@10
|
16 Copyright (C) 2003 Matteo Frigo.
|
|
Chris@10
|
17
|
|
Chris@10
|
18 Copyright (C) 2003 Massachusetts Institute of Technology.
|
|
Chris@10
|
19
|
|
Chris@10
|
20 Permission is granted to make and distribute verbatim copies of
|
|
Chris@10
|
21 this manual provided the copyright notice and this permission
|
|
Chris@10
|
22 notice are preserved on all copies.
|
|
Chris@10
|
23
|
|
Chris@10
|
24 Permission is granted to copy and distribute modified versions of
|
|
Chris@10
|
25 this manual under the conditions for verbatim copying, provided
|
|
Chris@10
|
26 that the entire resulting derived work is distributed under the
|
|
Chris@10
|
27 terms of a permission notice identical to this one.
|
|
Chris@10
|
28
|
|
Chris@10
|
29 Permission is granted to copy and distribute translations of this
|
|
Chris@10
|
30 manual into another language, under the above conditions for
|
|
Chris@10
|
31 modified versions, except that this permission notice may be
|
|
Chris@10
|
32 stated in a translation approved by the Free Software Foundation.
|
|
Chris@10
|
33 -->
|
|
Chris@10
|
34 <meta http-equiv="Content-Style-Type" content="text/css">
|
|
Chris@10
|
35 <style type="text/css"><!--
|
|
Chris@10
|
36 pre.display { font-family:inherit }
|
|
Chris@10
|
37 pre.format { font-family:inherit }
|
|
Chris@10
|
38 pre.smalldisplay { font-family:inherit; font-size:smaller }
|
|
Chris@10
|
39 pre.smallformat { font-family:inherit; font-size:smaller }
|
|
Chris@10
|
40 pre.smallexample { font-size:smaller }
|
|
Chris@10
|
41 pre.smalllisp { font-size:smaller }
|
|
Chris@10
|
42 span.sc { font-variant:small-caps }
|
|
Chris@10
|
43 span.roman { font-family:serif; font-weight:normal; }
|
|
Chris@10
|
44 span.sansserif { font-family:sans-serif; font-weight:normal; }
|
|
Chris@10
|
45 --></style>
|
|
Chris@10
|
46 </head>
|
|
Chris@10
|
47 <body>
|
|
Chris@10
|
48 <div class="node">
|
|
Chris@10
|
49 <a name="Complex-Multi-Dimensional-DFTs"></a>
|
|
Chris@10
|
50 <a name="Complex-Multi_002dDimensional-DFTs"></a>
|
|
Chris@10
|
51 <p>
|
|
Chris@10
|
52 Next: <a rel="next" accesskey="n" href="One_002dDimensional-DFTs-of-Real-Data.html#One_002dDimensional-DFTs-of-Real-Data">One-Dimensional DFTs of Real Data</a>,
|
|
Chris@10
|
53 Previous: <a rel="previous" accesskey="p" href="Complex-One_002dDimensional-DFTs.html#Complex-One_002dDimensional-DFTs">Complex One-Dimensional DFTs</a>,
|
|
Chris@10
|
54 Up: <a rel="up" accesskey="u" href="Tutorial.html#Tutorial">Tutorial</a>
|
|
Chris@10
|
55 <hr>
|
|
Chris@10
|
56 </div>
|
|
Chris@10
|
57
|
|
Chris@10
|
58 <h3 class="section">2.2 Complex Multi-Dimensional DFTs</h3>
|
|
Chris@10
|
59
|
|
Chris@10
|
60 <p>Multi-dimensional transforms work much the same way as one-dimensional
|
|
Chris@10
|
61 transforms: you allocate arrays of <code>fftw_complex</code> (preferably
|
|
Chris@10
|
62 using <code>fftw_malloc</code>), create an <code>fftw_plan</code>, execute it as
|
|
Chris@10
|
63 many times as you want with <code>fftw_execute(plan)</code>, and clean up
|
|
Chris@10
|
64 with <code>fftw_destroy_plan(plan)</code> (and <code>fftw_free</code>).
|
|
Chris@10
|
65
|
|
Chris@10
|
66 <p>FFTW provides two routines for creating plans for 2d and 3d transforms,
|
|
Chris@10
|
67 and one routine for creating plans of arbitrary dimensionality.
|
|
Chris@10
|
68 The 2d and 3d routines have the following signature:
|
|
Chris@10
|
69 <pre class="example"> fftw_plan fftw_plan_dft_2d(int n0, int n1,
|
|
Chris@10
|
70 fftw_complex *in, fftw_complex *out,
|
|
Chris@10
|
71 int sign, unsigned flags);
|
|
Chris@10
|
72 fftw_plan fftw_plan_dft_3d(int n0, int n1, int n2,
|
|
Chris@10
|
73 fftw_complex *in, fftw_complex *out,
|
|
Chris@10
|
74 int sign, unsigned flags);
|
|
Chris@10
|
75 </pre>
|
|
Chris@10
|
76 <p><a name="index-fftw_005fplan_005fdft_005f2d-39"></a><a name="index-fftw_005fplan_005fdft_005f3d-40"></a>
|
|
Chris@10
|
77 These routines create plans for <code>n0</code> by <code>n1</code> two-dimensional
|
|
Chris@10
|
78 (2d) transforms and <code>n0</code> by <code>n1</code> by <code>n2</code> 3d transforms,
|
|
Chris@10
|
79 respectively. All of these transforms operate on contiguous arrays in
|
|
Chris@10
|
80 the C-standard <dfn>row-major</dfn> order, so that the last dimension has the
|
|
Chris@10
|
81 fastest-varying index in the array. This layout is described further in
|
|
Chris@10
|
82 <a href="Multi_002ddimensional-Array-Format.html#Multi_002ddimensional-Array-Format">Multi-dimensional Array Format</a>.
|
|
Chris@10
|
83
|
|
Chris@10
|
84 <p>FFTW can also compute transforms of higher dimensionality. In order to
|
|
Chris@10
|
85 avoid confusion between the various meanings of the the word
|
|
Chris@10
|
86 “dimension”, we use the term <em>rank</em>
|
|
Chris@10
|
87 <a name="index-rank-41"></a>to denote the number of independent indices in an array.<a rel="footnote" href="#fn-1" name="fnd-1"><sup>1</sup></a> For
|
|
Chris@10
|
88 example, we say that a 2d transform has rank 2, a 3d transform has
|
|
Chris@10
|
89 rank 3, and so on. You can plan transforms of arbitrary rank by
|
|
Chris@10
|
90 means of the following function:
|
|
Chris@10
|
91
|
|
Chris@10
|
92 <pre class="example"> fftw_plan fftw_plan_dft(int rank, const int *n,
|
|
Chris@10
|
93 fftw_complex *in, fftw_complex *out,
|
|
Chris@10
|
94 int sign, unsigned flags);
|
|
Chris@10
|
95 </pre>
|
|
Chris@10
|
96 <p><a name="index-fftw_005fplan_005fdft-42"></a>
|
|
Chris@10
|
97 Here, <code>n</code> is a pointer to an array <code>n[rank]</code> denoting an
|
|
Chris@10
|
98 <code>n[0]</code> by <code>n[1]</code> by <small class="dots">...</small> by <code>n[rank-1]</code> transform.
|
|
Chris@10
|
99 Thus, for example, the call
|
|
Chris@10
|
100 <pre class="example"> fftw_plan_dft_2d(n0, n1, in, out, sign, flags);
|
|
Chris@10
|
101 </pre>
|
|
Chris@10
|
102 <p>is equivalent to the following code fragment:
|
|
Chris@10
|
103 <pre class="example"> int n[2];
|
|
Chris@10
|
104 n[0] = n0;
|
|
Chris@10
|
105 n[1] = n1;
|
|
Chris@10
|
106 fftw_plan_dft(2, n, in, out, sign, flags);
|
|
Chris@10
|
107 </pre>
|
|
Chris@10
|
108 <p><code>fftw_plan_dft</code> is not restricted to 2d and 3d transforms,
|
|
Chris@10
|
109 however, but it can plan transforms of arbitrary rank.
|
|
Chris@10
|
110
|
|
Chris@10
|
111 <p>You may have noticed that all the planner routines described so far
|
|
Chris@10
|
112 have overlapping functionality. For example, you can plan a 1d or 2d
|
|
Chris@10
|
113 transform by using <code>fftw_plan_dft</code> with a <code>rank</code> of <code>1</code>
|
|
Chris@10
|
114 or <code>2</code>, or even by calling <code>fftw_plan_dft_3d</code> with <code>n0</code>
|
|
Chris@10
|
115 and/or <code>n1</code> equal to <code>1</code> (with no loss in efficiency). This
|
|
Chris@10
|
116 pattern continues, and FFTW's planning routines in general form a
|
|
Chris@10
|
117 “partial order,” sequences of
|
|
Chris@10
|
118 <a name="index-partial-order-43"></a>interfaces with strictly increasing generality but correspondingly
|
|
Chris@10
|
119 greater complexity.
|
|
Chris@10
|
120
|
|
Chris@10
|
121 <p><code>fftw_plan_dft</code> is the most general complex-DFT routine that we
|
|
Chris@10
|
122 describe in this tutorial, but there are also the advanced and guru interfaces,
|
|
Chris@10
|
123 <a name="index-advanced-interface-44"></a><a name="index-guru-interface-45"></a>which allow one to efficiently combine multiple/strided transforms
|
|
Chris@10
|
124 into a single FFTW plan, transform a subset of a larger
|
|
Chris@10
|
125 multi-dimensional array, and/or to handle more general complex-number
|
|
Chris@10
|
126 formats. For more information, see <a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a>.
|
|
Chris@10
|
127
|
|
Chris@10
|
128 <!-- -->
|
|
Chris@10
|
129 <div class="footnote">
|
|
Chris@10
|
130 <hr>
|
|
Chris@10
|
131 <h4>Footnotes</h4><p class="footnote"><small>[<a name="fn-1" href="#fnd-1">1</a>]</small> The
|
|
Chris@10
|
132 term “rank” is commonly used in the APL, FORTRAN, and Common Lisp
|
|
Chris@10
|
133 traditions, although it is not so common in the C world.</p>
|
|
Chris@10
|
134
|
|
Chris@10
|
135 <hr></div>
|
|
Chris@10
|
136
|
|
Chris@10
|
137 </body></html>
|
|
Chris@10
|
138
|
