Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
2 | pj | 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> |
2 | <HTML> |
||
3 | <HEAD> |
||
4 | <!-- This HTML file has been created by texi2html 1.52 |
||
5 | from fftw.texi on 18 May 1999 --> |
||
6 | |||
7 | <TITLE>FFTW - FFTW Reference</TITLE> |
||
8 | </HEAD> |
||
9 | <BODY TEXT="#000000" BGCOLOR="#FFFFFF"> |
||
10 | Go to the <A HREF="fftw_1.html">first</A>, <A HREF="fftw_2.html">previous</A>, <A HREF="fftw_4.html">next</A>, <A HREF="fftw_10.html">last</A> section, <A HREF="fftw_toc.html">table of contents</A>. |
||
11 | <P><HR><P> |
||
12 | |||
13 | |||
14 | <H1><A NAME="SEC16">FFTW Reference</A></H1> |
||
15 | |||
16 | <P> |
||
17 | This chapter provides a complete reference for all sequential (i.e., |
||
18 | one-processor) FFTW functions. We first define the data types upon |
||
19 | which FFTW operates, that is, real, complex, and "halfcomplex" numbers |
||
20 | (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>). Then, in four sections, we explain the FFTW |
||
21 | program interface for complex one-dimensional transforms |
||
22 | (see Section <A HREF="fftw_3.html#SEC18">One-dimensional Transforms Reference</A>), complex |
||
23 | multi-dimensional transforms (see Section <A HREF="fftw_3.html#SEC24">Multi-dimensional Transforms Reference</A>), and real one-dimensional transforms (see Section <A HREF="fftw_3.html#SEC29">Real One-dimensional Transforms Reference</A>), real multi-dimensional |
||
24 | transforms (see Section <A HREF="fftw_3.html#SEC34">Real Multi-dimensional Transforms Reference</A>). |
||
25 | Section <A HREF="fftw_3.html#SEC41">Wisdom Reference</A> describes the <CODE>wisdom</CODE> mechanism for |
||
26 | exporting and importing plans. Finally, Section <A HREF="fftw_3.html#SEC45">Memory Allocator Reference</A> describes how to change FFTW's default memory allocator. |
||
27 | For parallel transforms, See Section <A HREF="fftw_4.html#SEC47">Parallel FFTW</A>. |
||
28 | |||
29 | |||
30 | |||
31 | |||
32 | <H2><A NAME="SEC17">Data Types</A></H2> |
||
33 | <P> |
||
34 | <A NAME="IDX98"></A> |
||
35 | <A NAME="IDX99"></A> |
||
36 | <A NAME="IDX100"></A> |
||
37 | |||
38 | |||
39 | <P> |
||
40 | The routines in the FFTW package use three main kinds of data types. |
||
41 | <EM>Real</EM> and <EM>complex</EM> numbers should be already known to the |
||
42 | reader. We also use the term <EM>halfcomplex</EM> to describe complex |
||
43 | arrays in a special packed format used by the one-dimensional real |
||
44 | transforms (taking advantage of the <EM>hermitian</EM> symmetry that arises |
||
45 | in those cases). |
||
46 | |||
47 | |||
48 | <P> |
||
49 | By including <CODE><fftw.h></CODE> or <CODE><rfftw.h></CODE>, you will have access |
||
50 | to the following definitions: |
||
51 | |||
52 | |||
53 | |||
54 | <PRE> |
||
55 | typedef double fftw_real; |
||
56 | |||
57 | typedef struct { |
||
58 | fftw_real re, im; |
||
59 | } fftw_complex; |
||
60 | |||
61 | #define c_re(c) ((c).re) |
||
62 | #define c_im(c) ((c).im) |
||
63 | </PRE> |
||
64 | |||
65 | <P> |
||
66 | <A NAME="IDX101"></A> |
||
67 | <A NAME="IDX102"></A> |
||
68 | |||
69 | |||
70 | <P> |
||
71 | All FFTW operations are performed on the <CODE>fftw_real</CODE> and |
||
72 | <CODE>fftw_complex</CODE> data types. For <CODE>fftw_complex</CODE> numbers, the |
||
73 | two macros <CODE>c_re</CODE> and <CODE>c_im</CODE> retrieve, respectively, the real |
||
74 | and imaginary parts of the number. |
||
75 | |||
76 | |||
77 | <P> |
||
78 | A <EM>real array</EM> is an array of real numbers. A <EM>complex array</EM> |
||
79 | is an array of complex numbers. A one-dimensional array X of |
||
80 | n complex numbers is <EM>hermitian</EM> if the following property |
||
81 | holds: |
||
82 | for all 0 <= i < n, we have X<sub>i</sub> = conj(X<sub>n-i</sub>)}. |
||
83 | Hermitian arrays are relevant to FFTW because the Fourier transform of a |
||
84 | real array is hermitian. |
||
85 | |||
86 | |||
87 | <P> |
||
88 | Because of its symmetry, a hermitian array can be stored in half the |
||
89 | space of a complex array of the same size. FFTW's one-dimensional real |
||
90 | transforms store hermitian arrays as <EM>halfcomplex</EM> arrays. A |
||
91 | halfcomplex array of size n is |
||
92 | <A NAME="IDX103"></A> |
||
93 | a one-dimensional array of n <CODE>fftw_real</CODE> numbers. A |
||
94 | hermitian array X in stored into a halfcomplex array Y as |
||
95 | follows. |
||
96 | For all integers i such that 0 <= i <= n / 2, we have |
||
97 | Y<sub>i</sub> = Re(X<sub>i</sub>). For all integers i such that 0 |
||
98 | < i < n / 2, we have Y<sub>n-i</sub> = Im(X<sub>i</sub>). |
||
99 | |||
100 | |||
101 | <P> |
||
102 | We now illustrate halfcomplex storage for n = 4 and n = 5, |
||
103 | since the scheme depends on the parity of n. Let n = 4. |
||
104 | In this case, we have |
||
105 | Y<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>), |
||
106 | Y<sub>2</sub> = Re(X<sub>2</sub>), and Y<sub>3</sub> = Im(X<sub>1</sub>). |
||
107 | Let now n = 5. In this case, we have |
||
108 | Y<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>), |
||
109 | Y<sub>2</sub> = Re(X<sub>2</sub>), Y<sub>3</sub> = Im(X<sub>2</sub>), |
||
110 | and Y<sub>4</sub> = Im(X<sub>1</sub>). |
||
111 | |||
112 | |||
113 | <P> |
||
114 | <A NAME="IDX104"></A> |
||
115 | By default, the type <CODE>fftw_real</CODE> equals the C type <CODE>double</CODE>. |
||
116 | To work in single precision rather than double precision, <CODE>#define</CODE> |
||
117 | the symbol <CODE>FFTW_ENABLE_FLOAT</CODE> in <CODE>fftw.h</CODE> and then recompile |
||
118 | the library. On Unix systems, you can instead use <CODE>configure |
||
119 | --enable-float</CODE> at installation time (see Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A>). |
||
120 | <A NAME="IDX105"></A> |
||
121 | <A NAME="IDX106"></A> |
||
122 | |||
123 | |||
124 | <P> |
||
125 | In version 1 of FFTW, the data types were called <CODE>FFTW_REAL</CODE> and |
||
126 | <CODE>FFTW_COMPLEX</CODE>. We changed the capitalization for consistency with |
||
127 | the rest of FFTW's conventions. The old names are still supported, but |
||
128 | their use is deprecated. |
||
129 | <A NAME="IDX107"></A> |
||
130 | <A NAME="IDX108"></A> |
||
131 | |||
132 | |||
133 | |||
134 | |||
135 | <H2><A NAME="SEC18">One-dimensional Transforms Reference</A></H2> |
||
136 | |||
137 | <P> |
||
138 | The one-dimensional complex routines are generally prefixed with |
||
139 | <CODE>fftw_</CODE>. Programs using FFTW should be linked with <CODE>-lfftw |
||
140 | -lm</CODE> on Unix systems, or with the FFTW and standard math libraries in |
||
141 | general. |
||
142 | |||
143 | |||
144 | |||
145 | |||
146 | <H3><A NAME="SEC19">Plan Creation for One-dimensional Transforms</A></H3> |
||
147 | |||
148 | |||
149 | <PRE> |
||
150 | #include <fftw.h> |
||
151 | |||
152 | fftw_plan fftw_create_plan(int n, fftw_direction dir, |
||
153 | int flags); |
||
154 | |||
155 | fftw_plan fftw_create_plan_specific(int n, fftw_direction dir, |
||
156 | int flags, |
||
157 | fftw_complex *in, int istride, |
||
158 | fftw_complex *out, int ostride); |
||
159 | </PRE> |
||
160 | |||
161 | <P> |
||
162 | <A NAME="IDX109"></A> |
||
163 | <A NAME="IDX110"></A> |
||
164 | <A NAME="IDX111"></A> |
||
165 | <A NAME="IDX112"></A> |
||
166 | |||
167 | |||
168 | <P> |
||
169 | The function <CODE>fftw_create_plan</CODE> creates a plan, which is |
||
170 | a data structure containing all the information that <CODE>fftw</CODE> |
||
171 | needs in order to compute the 1D Fourier transform. You can |
||
172 | create as many plans as you need, but only one plan for a given |
||
173 | array size is required (a plan can be reused many times). |
||
174 | |||
175 | |||
176 | <P> |
||
177 | <CODE>fftw_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> |
||
178 | if, for some reason, the plan can't be created. In the |
||
179 | default installation, this cannot happen, but it is possible |
||
180 | to configure FFTW in such a way that some input sizes are |
||
181 | forbidden, and FFTW cannot create a plan. |
||
182 | |||
183 | |||
184 | <P> |
||
185 | The <CODE>fftw_create_plan_specific</CODE> variant takes as additional |
||
186 | arguments specific input/output arrays and their strides. For the last |
||
187 | four arguments, you should pass the arrays and strides that you will |
||
188 | eventually be passing to <CODE>fftw</CODE>. The resulting plans will be |
||
189 | optimized for those arrays and strides, although they may be used on |
||
190 | other arrays as well. Note: the contents of the in and out arrays are |
||
191 | <EM>destroyed</EM> by the specific planner (the initial contents are |
||
192 | ignored, so the arrays need not have been initialized). |
||
193 | |||
194 | |||
195 | |||
196 | <H4>Arguments</H4> |
||
197 | |||
198 | <UL> |
||
199 | <LI> |
||
200 | |||
201 | <CODE>n</CODE> is the size of the transform. It can be |
||
202 | any positive integer. |
||
203 | |||
204 | |||
205 | <UL> |
||
206 | <LI> |
||
207 | |||
208 | FFTW is best at handling sizes of the form |
||
209 | 2<SUP>a</SUP> 3<SUP>b</SUP> 5<SUP>c</SUP> 7<SUP>d</SUP> |
||
210 | 11<SUP>e</SUP> 13<SUP>f</SUP>, |
||
211 | where e+f is either 0 or |
||
212 | 1, and the other exponents are arbitrary. Other sizes are |
||
213 | computed by means of a slow, general-purpose routine (which nevertheless |
||
214 | retains |
||
215 | O(n lg n) |
||
216 | performance, even for prime sizes). (It is |
||
217 | possible to customize FFTW for different array sizes. |
||
218 | See Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A> for more information.) Transforms |
||
219 | whose sizes are powers of 2 are especially fast. |
||
220 | </UL> |
||
221 | |||
222 | <LI> |
||
223 | |||
224 | <CODE>dir</CODE> is the sign of the exponent in the formula that |
||
225 | defines the Fourier transform. It can be -1 or +1. |
||
226 | The aliases <CODE>FFTW_FORWARD</CODE> and <CODE>FFTW_BACKWARD</CODE> |
||
227 | are provided, where <CODE>FFTW_FORWARD</CODE> stands for -1. |
||
228 | |||
229 | <LI> |
||
230 | |||
231 | <A NAME="IDX113"></A> |
||
232 | <CODE>flags</CODE> is a boolean OR (<SAMP>`|'</SAMP>) of zero or more of the following: |
||
233 | |||
234 | <UL> |
||
235 | <LI> |
||
236 | |||
237 | <CODE>FFTW_MEASURE</CODE>: this flag tells FFTW to find the optimal plan by |
||
238 | actually <EM>computing</EM> several FFTs and measuring their |
||
239 | execution time. Depending on the installation, this can take some |
||
240 | time. <A NAME="DOCF2" HREF="fftw_foot.html#FOOT2">(2)</A> |
||
241 | |||
242 | <LI> |
||
243 | |||
244 | <CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable" |
||
245 | plan (for a RISC processor with many registers). If neither |
||
246 | <CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is |
||
247 | <CODE>FFTW_ESTIMATE</CODE>. |
||
248 | |||
249 | <LI> |
||
250 | |||
251 | <CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input and |
||
252 | output arrays will be distinct (this is the default). |
||
253 | <A NAME="IDX114"></A> |
||
254 | |||
255 | <LI> |
||
256 | |||
257 | <A NAME="IDX115"></A> |
||
258 | <CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want the output |
||
259 | in the input array. The algorithm used is not necessarily in place: |
||
260 | FFTW is able to compute true in-place transforms only for small values |
||
261 | of <CODE>n</CODE>. If FFTW is not able to compute the transform in-place, it |
||
262 | will allocate a temporary array (unless you provide one yourself), |
||
263 | compute the transform out of place, and copy the result back. |
||
264 | <EM>Warning: This option changes the meaning of some parameters of |
||
265 | <CODE>fftw</CODE></EM> (see Section <A HREF="fftw_3.html#SEC21">Computing the One-dimensional Transform</A>). |
||
266 | |||
267 | The in-place option is mainly provided for people who want to write |
||
268 | their own in-place multi-dimensional Fourier transform, using FFTW as a |
||
269 | base. For example, consider a three-dimensional <CODE>n * n * n</CODE> |
||
270 | transform. An out-of-place algorithm will need another array (which may |
||
271 | be huge). However, FFTW can compute the in-place transform along |
||
272 | each dimension using only a temporary array of size <CODE>n</CODE>. |
||
273 | Moreover, if FFTW happens to be able to compute the transform truly |
||
274 | in-place, no temporary array and no copying are needed. As distributed, |
||
275 | FFTW `knows' how to compute in-place transforms of size 1, 2, 3, 4, 5, 6, |
||
276 | 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 32 and 64. |
||
277 | |||
278 | The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>. |
||
279 | |||
280 | <LI> |
||
281 | |||
282 | <A NAME="IDX116"></A> |
||
283 | <CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help |
||
284 | in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.) |
||
285 | This can greatly speed the creation of plans, especially with the |
||
286 | <CODE>FFTW_MEASURE</CODE> option. <CODE>FFTW_ESTIMATE</CODE> plans can also take |
||
287 | advantage of <CODE>wisdom</CODE> to produce a more optimal plan (based on past |
||
288 | measurements) than the estimation heuristic would normally |
||
289 | generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE> |
||
290 | will also be generated if the current transform size is not completely |
||
291 | understood by existing <CODE>wisdom</CODE>. |
||
292 | |||
293 | </UL> |
||
294 | |||
295 | <LI> |
||
296 | |||
297 | <CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for |
||
298 | <CODE>fftw_create_plan_specific</CODE>): see corresponding arguments in the |
||
299 | description of <CODE>fftw</CODE>. (See Section <A HREF="fftw_3.html#SEC21">Computing the One-dimensional Transform</A>.) In particular, the <CODE>out</CODE> and <CODE>ostride</CODE> |
||
300 | parameters have the same special meaning for <CODE>FFTW_IN_PLACE</CODE> |
||
301 | transforms as they have for <CODE>fftw</CODE>. |
||
302 | |||
303 | </UL> |
||
304 | |||
305 | |||
306 | |||
307 | <H3><A NAME="SEC20">Discussion on Specific Plans</A></H3> |
||
308 | <P> |
||
309 | <A NAME="IDX117"></A> |
||
310 | We recommend the use of the specific planners, even in cases where you |
||
311 | will be transforming arrays different from those passed to the specific |
||
312 | planners, as they confer the following advantages: |
||
313 | |||
314 | |||
315 | |||
316 | <UL> |
||
317 | |||
318 | <LI> |
||
319 | |||
320 | The resulting plans will be optimized for your specific arrays and |
||
321 | strides. This may or may not make a significant difference, but it |
||
322 | certainly doesn't hurt. (The ordinary planner does its planning based |
||
323 | upon a stride-one temporary array that it allocates.) |
||
324 | |||
325 | <LI> |
||
326 | |||
327 | Less intermediate storage is required during the planning process. (The |
||
328 | ordinary planner uses O(<CODE>N</CODE>) temporary storage, where <CODE>N</CODE> is |
||
329 | the maximum dimension, while it is creating the plan.) |
||
330 | |||
331 | <LI> |
||
332 | |||
333 | For multi-dimensional transforms, new parameters become accessible for |
||
334 | optimization by the planner. (Since multi-dimensional arrays can be |
||
335 | very large, we don't dare to allocate one in the ordinary planner for |
||
336 | experimentation. This prevents us from doing certain optimizations |
||
337 | that can yield dramatic improvements in some cases.) |
||
338 | |||
339 | </UL> |
||
340 | |||
341 | <P> |
||
342 | On the other hand, note that <EM>the specific planner destroys the |
||
343 | contents of the <CODE>in</CODE> and <CODE>out</CODE> arrays</EM>. |
||
344 | |||
345 | |||
346 | |||
347 | |||
348 | <H3><A NAME="SEC21">Computing the One-dimensional Transform</A></H3> |
||
349 | |||
350 | |||
351 | <PRE> |
||
352 | #include <fftw.h> |
||
353 | |||
354 | void fftw(fftw_plan plan, int howmany, |
||
355 | fftw_complex *in, int istride, int idist, |
||
356 | fftw_complex *out, int ostride, int odist); |
||
357 | |||
358 | void fftw_one(fftw_plan plan, fftw_complex *in, |
||
359 | fftw_complex *out); |
||
360 | </PRE> |
||
361 | |||
362 | <P> |
||
363 | <A NAME="IDX118"></A> |
||
364 | <A NAME="IDX119"></A> |
||
365 | |||
366 | |||
367 | <P> |
||
368 | The function <CODE>fftw</CODE> computes the one-dimensional Fourier transform, |
||
369 | using a plan created by <CODE>fftw_create_plan</CODE> (See Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>.) The function |
||
370 | <CODE>fftw_one</CODE> provides a simplified interface for the common case of |
||
371 | single input array of stride 1. |
||
372 | <A NAME="IDX120"></A> |
||
373 | |||
374 | |||
375 | |||
376 | <H4>Arguments</H4> |
||
377 | |||
378 | <UL> |
||
379 | <LI> |
||
380 | |||
381 | <CODE>plan</CODE> is the plan created by <CODE>fftw_create_plan</CODE> |
||
382 | (see Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>). |
||
383 | |||
384 | <LI> |
||
385 | |||
386 | <CODE>howmany</CODE> is the number of transforms <CODE>fftw</CODE> will compute. |
||
387 | It is faster to tell FFTW to compute many transforms, instead of |
||
388 | simply calling <CODE>fftw</CODE> many times. |
||
389 | |||
390 | <LI> |
||
391 | |||
392 | <CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s). |
||
393 | There are <CODE>howmany</CODE> input arrays; the first one is pointed to by |
||
394 | <CODE>in</CODE>, the second one is pointed to by <CODE>in + idist</CODE>, and so on, |
||
395 | up to <CODE>in + (howmany - 1) * idist</CODE>. Each input array consists of |
||
396 | complex numbers (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>), which are not necessarily |
||
397 | contiguous in memory. Specifically, <CODE>in[0]</CODE> is the first element |
||
398 | of the first array, <CODE>in[istride]</CODE> is the second element of the |
||
399 | first array, and so on. In general, the <CODE>i</CODE>-th element of the |
||
400 | <CODE>j</CODE>-th input array will be in position <CODE>in[i * istride + j * |
||
401 | idist]</CODE>. |
||
402 | |||
403 | <LI> |
||
404 | |||
405 | <CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output |
||
406 | array(s). The format is the same as for the input array. |
||
407 | |||
408 | |||
409 | <UL> |
||
410 | <LI><EM>In-place transforms</EM>: |
||
411 | |||
412 | <A NAME="IDX121"></A> |
||
413 | If the <CODE>plan</CODE> specifies an in-place transform, <CODE>ostride</CODE> and |
||
414 | <CODE>odist</CODE> are always ignored. If <CODE>out</CODE> is <CODE>NULL</CODE>, |
||
415 | <CODE>out</CODE> is ignored, too. Otherwise, <CODE>out</CODE> is interpreted as a |
||
416 | pointer to an array of <CODE>n</CODE> complex numbers, that FFTW will use as |
||
417 | temporary space to perform the in-place computation. <CODE>out</CODE> is used |
||
418 | as scratch space and its contents destroyed. In this case, <CODE>out</CODE> |
||
419 | must be an ordinary array whose elements are contiguous in memory (no |
||
420 | striding). |
||
421 | </UL> |
||
422 | |||
423 | </UL> |
||
424 | |||
425 | <P> |
||
426 | The function <CODE>fftw_one</CODE> transforms a single, contiguous input array |
||
427 | to a contiguous output array. By definition, the call |
||
428 | |||
429 | <PRE> |
||
430 | fftw_one(plan, in, out) |
||
431 | </PRE> |
||
432 | |||
433 | <P> |
||
434 | is equivalent to |
||
435 | |||
436 | <PRE> |
||
437 | fftw(plan, 1, in, 1, 1, out, 1, 1) |
||
438 | </PRE> |
||
439 | |||
440 | |||
441 | |||
442 | <H3><A NAME="SEC22">Destroying a One-dimensional Plan</A></H3> |
||
443 | |||
444 | |||
445 | <PRE> |
||
446 | #include <fftw.h> |
||
447 | |||
448 | void fftw_destroy_plan(fftw_plan plan); |
||
449 | </PRE> |
||
450 | |||
451 | <P> |
||
452 | <A NAME="IDX122"></A> |
||
453 | |||
454 | |||
455 | <P> |
||
456 | The function <CODE>fftw_destroy_plan</CODE> frees the plan <CODE>plan</CODE> and |
||
457 | releases all the memory associated with it. After destruction, a plan |
||
458 | is no longer valid. |
||
459 | |||
460 | |||
461 | |||
462 | |||
463 | <H3><A NAME="SEC23">What FFTW Really Computes</A></H3> |
||
464 | <P> |
||
465 | <A NAME="IDX123"></A> |
||
466 | In this section, we define precisely what FFTW computes. Please be |
||
467 | warned that different authors and software packages might employ |
||
468 | different conventions than FFTW does. |
||
469 | |||
470 | |||
471 | <P> |
||
472 | The forward transform of a complex array X of size |
||
473 | n computes an array Y, where |
||
474 | <center><IMG SRC="equation-1.gif" ALIGN="top"></center> |
||
475 | |||
476 | |||
477 | <P> |
||
478 | The backward transform computes |
||
479 | <center><IMG SRC="equation-2.gif" ALIGN="top"></center> |
||
480 | |||
481 | |||
482 | <P> |
||
483 | <A NAME="IDX124"></A> |
||
484 | FFTW computes an unnormalized transform, that is, the equation |
||
485 | IFFT(FFT(X)) = n X holds. In other words, applying the forward |
||
486 | and then the backward transform will multiply the input by n. |
||
487 | |||
488 | |||
489 | <P> |
||
490 | <A NAME="IDX125"></A> |
||
491 | An <CODE>FFTW_FORWARD</CODE> transform corresponds to a sign of -1 in |
||
492 | the exponent of the DFT. Note also that we use the standard |
||
493 | "in-order" output ordering--the k-th output corresponds to the |
||
494 | frequency k/n (or k/T, where T is your total |
||
495 | sampling period). For those who like to think in terms of positive and |
||
496 | negative frequencies, this means that the positive frequencies are |
||
497 | stored in the first half of the output and the negative frequencies are |
||
498 | stored in backwards order in the second half of the output. (The |
||
499 | frequency -k/n is the same as the frequency (n-k)/n.) |
||
500 | |||
501 | |||
502 | |||
503 | |||
504 | <H2><A NAME="SEC24">Multi-dimensional Transforms Reference</A></H2> |
||
505 | <P> |
||
506 | <A NAME="IDX126"></A> |
||
507 | <A NAME="IDX127"></A> |
||
508 | The multi-dimensional complex routines are generally prefixed with |
||
509 | <CODE>fftwnd_</CODE>. Programs using FFTWND should be linked with <CODE>-lfftw |
||
510 | -lm</CODE> on Unix systems, or with the FFTW and standard math libraries in |
||
511 | general. |
||
512 | <A NAME="IDX128"></A> |
||
513 | |||
514 | |||
515 | |||
516 | |||
517 | <H3><A NAME="SEC25">Plan Creation for Multi-dimensional Transforms</A></H3> |
||
518 | |||
519 | |||
520 | <PRE> |
||
521 | #include <fftw.h> |
||
522 | |||
523 | fftwnd_plan fftwnd_create_plan(int rank, const int *n, |
||
524 | fftw_direction dir, int flags); |
||
525 | |||
526 | fftwnd_plan fftw2d_create_plan(int nx, int ny, |
||
527 | fftw_direction dir, int flags); |
||
528 | |||
529 | fftwnd_plan fftw3d_create_plan(int nx, int ny, int nz, |
||
530 | fftw_direction dir, int flags); |
||
531 | |||
532 | fftwnd_plan fftwnd_create_plan_specific(int rank, const int *n, |
||
533 | fftw_direction dir, |
||
534 | int flags, |
||
535 | fftw_complex *in, int istride, |
||
536 | fftw_complex *out, int ostride); |
||
537 | |||
538 | fftwnd_plan fftw2d_create_plan_specific(int nx, int ny, |
||
539 | fftw_direction dir, |
||
540 | int flags, |
||
541 | fftw_complex *in, int istride, |
||
542 | fftw_complex *out, int ostride); |
||
543 | |||
544 | fftwnd_plan fftw3d_create_plan_specific(int nx, int ny, int nz, |
||
545 | fftw_direction dir, int flags, |
||
546 | fftw_complex *in, int istride, |
||
547 | fftw_complex *out, int ostride); |
||
548 | </PRE> |
||
549 | |||
550 | <P> |
||
551 | <A NAME="IDX129"></A> |
||
552 | <A NAME="IDX130"></A> |
||
553 | <A NAME="IDX131"></A> |
||
554 | <A NAME="IDX132"></A> |
||
555 | <A NAME="IDX133"></A> |
||
556 | <A NAME="IDX134"></A> |
||
557 | <A NAME="IDX135"></A> |
||
558 | <A NAME="IDX136"></A> |
||
559 | |||
560 | |||
561 | <P> |
||
562 | The function <CODE>fftwnd_create_plan</CODE> creates a plan, which is a data |
||
563 | structure containing all the information that <CODE>fftwnd</CODE> needs in |
||
564 | order to compute a multi-dimensional Fourier transform. You can create |
||
565 | as many plans as you need, but only one plan for a given array size is |
||
566 | required (a plan can be reused many times). The functions |
||
567 | <CODE>fftw2d_create_plan</CODE> and <CODE>fftw3d_create_plan</CODE> are optional, |
||
568 | alternative interfaces to <CODE>fftwnd_create_plan</CODE> for two and three |
||
569 | dimensions, respectively. |
||
570 | |||
571 | |||
572 | <P> |
||
573 | <CODE>fftwnd_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> if, for |
||
574 | some reason, the plan can't be created. This can happen if memory runs |
||
575 | out or if the arguments are invalid in some way (e.g. if <CODE>rank</CODE> < |
||
576 | 0). |
||
577 | |||
578 | |||
579 | <P> |
||
580 | The <CODE>create_plan_specific</CODE> variants take as additional arguments |
||
581 | specific input/output arrays and their strides. For the last four |
||
582 | arguments, you should pass the arrays and strides that you will |
||
583 | eventually be passing to <CODE>fftwnd</CODE>. The resulting plans will be |
||
584 | optimized for those arrays and strides, although they may be used on |
||
585 | other arrays as well. Note: the contents of the in and out arrays are |
||
586 | <EM>destroyed</EM> by the specific planner (the initial contents are |
||
587 | ignored, so the arrays need not have been initialized). |
||
588 | See Section <A HREF="fftw_3.html#SEC20">Discussion on Specific Plans</A>, for a discussion on specific plans. |
||
589 | |||
590 | |||
591 | |||
592 | <H4>Arguments</H4> |
||
593 | |||
594 | <UL> |
||
595 | <LI> |
||
596 | |||
597 | <CODE>rank</CODE> is the dimensionality of the arrays to be transformed. It |
||
598 | can be any non-negative integer. |
||
599 | |||
600 | <LI> |
||
601 | |||
602 | <CODE>n</CODE> is a pointer to an array of <CODE>rank</CODE> integers, giving the |
||
603 | size of each dimension of the arrays to be transformed. These sizes, |
||
604 | which must be positive integers, correspond to the dimensions of |
||
605 | <A NAME="IDX137"></A> |
||
606 | row-major arrays--i.e. <CODE>n[0]</CODE> is the size of the dimension whose |
||
607 | indices vary most slowly, and so on. (See Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>, for more information on row-major storage.) |
||
608 | See Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>, |
||
609 | for more information regarding optimal array sizes. |
||
610 | |||
611 | <LI> |
||
612 | |||
613 | <CODE>nx</CODE> and <CODE>ny</CODE> in <CODE>fftw2d_create_plan</CODE> are positive |
||
614 | integers specifying the dimensions of the rank 2 array to be |
||
615 | transformed. i.e. they specify that the transform will operate on |
||
616 | <CODE>nx x ny</CODE> arrays in row-major order, where <CODE>nx</CODE> is the number |
||
617 | of rows and <CODE>ny</CODE> is the number of columns. |
||
618 | |||
619 | <LI> |
||
620 | |||
621 | <CODE>nx</CODE>, <CODE>ny</CODE> and <CODE>nz</CODE> in <CODE>fftw3d_create_plan</CODE> are |
||
622 | positive integers specifying the dimensions of the rank 3 array to be |
||
623 | transformed. i.e. they specify that the transform will operate on |
||
624 | <CODE>nx x ny x nz</CODE> arrays in row-major order. |
||
625 | |||
626 | <LI> |
||
627 | |||
628 | <CODE>dir</CODE> is the sign of the exponent in the formula that defines the |
||
629 | Fourier transform. It can be -1 or +1. The aliases |
||
630 | <CODE>FFTW_FORWARD</CODE> and <CODE>FFTW_BACKWARD</CODE> are provided, where |
||
631 | <CODE>FFTW_FORWARD</CODE> stands for -1. |
||
632 | |||
633 | <LI> |
||
634 | |||
635 | <A NAME="IDX138"></A> |
||
636 | <CODE>flags</CODE> is a boolean OR (<SAMP>`|'</SAMP>) of zero or more of the following: |
||
637 | |||
638 | <UL> |
||
639 | <LI> |
||
640 | |||
641 | <CODE>FFTW_MEASURE</CODE>: this flag tells FFTW to find the optimal plan by |
||
642 | actually <EM>computing</EM> several FFTs and measuring their execution |
||
643 | time. |
||
644 | |||
645 | <LI> |
||
646 | |||
647 | <CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable" |
||
648 | plan (for a RISC processor with many registers). If neither |
||
649 | <CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is |
||
650 | <CODE>FFTW_ESTIMATE</CODE>. |
||
651 | |||
652 | <LI> |
||
653 | |||
654 | <CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input |
||
655 | and output arrays will be distinct (this is the default). |
||
656 | |||
657 | <LI> |
||
658 | |||
659 | <CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want to perform |
||
660 | the transform in-place. (Unlike the one-dimensional transform, this |
||
661 | "really" <A NAME="DOCF3" HREF="fftw_foot.html#FOOT3">(3)</A> performs the |
||
662 | transform in-place.) Note that, if you want to perform in-place |
||
663 | transforms, you <EM>must</EM> use a plan created with this option. |
||
664 | |||
665 | The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>. |
||
666 | |||
667 | <LI> |
||
668 | |||
669 | <A NAME="IDX139"></A> |
||
670 | <CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help |
||
671 | in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.) This can greatly |
||
672 | speed the creation of plans, especially with the <CODE>FFTW_MEASURE</CODE> |
||
673 | option. <CODE>FFTW_ESTIMATE</CODE> plans can also take advantage of |
||
674 | <CODE>wisdom</CODE> to produce a more optimal plan (based on past |
||
675 | measurements) than the estimation heuristic would normally |
||
676 | generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE> |
||
677 | will also be generated if the current transform size is not completely |
||
678 | understood by existing <CODE>wisdom</CODE>. Note that the same <CODE>wisdom</CODE> |
||
679 | is shared between one-dimensional and multi-dimensional transforms. |
||
680 | |||
681 | </UL> |
||
682 | |||
683 | <LI> |
||
684 | |||
685 | <CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for the |
||
686 | <CODE>_create_plan_specific</CODE> variants): see corresponding arguments in |
||
687 | the description of <CODE>fftwnd</CODE>. (See Section <A HREF="fftw_3.html#SEC26">Computing the Multi-dimensional Transform</A>.) |
||
688 | |||
689 | </UL> |
||
690 | |||
691 | |||
692 | |||
693 | <H3><A NAME="SEC26">Computing the Multi-dimensional Transform</A></H3> |
||
694 | |||
695 | |||
696 | <PRE> |
||
697 | #include <fftw.h> |
||
698 | |||
699 | void fftwnd(fftwnd_plan plan, int howmany, |
||
700 | fftw_complex *in, int istride, int idist, |
||
701 | fftw_complex *out, int ostride, int odist); |
||
702 | |||
703 | void fftwnd_one(fftwnd_plan p, fftw_complex *in, |
||
704 | fftw_complex *out); |
||
705 | </PRE> |
||
706 | |||
707 | <P> |
||
708 | <A NAME="IDX140"></A> |
||
709 | <A NAME="IDX141"></A> |
||
710 | |||
711 | |||
712 | <P> |
||
713 | The function <CODE>fftwnd</CODE> computes the multi-dimensional Fourier |
||
714 | Transform, using a plan created by <CODE>fftwnd_create_plan</CODE> |
||
715 | (see Section <A HREF="fftw_3.html#SEC25">Plan Creation for Multi-dimensional Transforms</A>). (Note that the plan determines the rank and dimensions of |
||
716 | the array to be transformed.) The function <CODE>fftwnd_one</CODE> provides a |
||
717 | simplified interface for the common case of single input array of stride |
||
718 | 1. |
||
719 | <A NAME="IDX142"></A> |
||
720 | |||
721 | |||
722 | |||
723 | <H4>Arguments</H4> |
||
724 | |||
725 | <UL> |
||
726 | <LI> |
||
727 | |||
728 | <CODE>plan</CODE> is the plan created by <CODE>fftwnd_create_plan</CODE>. |
||
729 | (see Section <A HREF="fftw_3.html#SEC25">Plan Creation for Multi-dimensional Transforms</A>). In the case of two and three-dimensional transforms, it |
||
730 | could also have been created by <CODE>fftw2d_create_plan</CODE> or |
||
731 | <CODE>fftw3d_create_plan</CODE>, respectively. |
||
732 | |||
733 | <LI> |
||
734 | |||
735 | <CODE>howmany</CODE> is the number of transforms <CODE>fftwnd</CODE> will compute. |
||
736 | |||
737 | <LI> |
||
738 | |||
739 | <CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s). |
||
740 | There are <CODE>howmany</CODE> input arrays; the first one is pointed to by |
||
741 | <CODE>in</CODE>, the second one is pointed to by <CODE>in + idist</CODE>, and so on, |
||
742 | up to <CODE>in + (howmany - 1) * idist</CODE>. Each input array consists of |
||
743 | complex numbers (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>), stored in row-major format |
||
744 | (see Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>), which are not necessarily |
||
745 | contiguous in memory. Specifically, <CODE>in[0]</CODE> is the first element |
||
746 | of the first array, <CODE>in[istride]</CODE> is the second element of the |
||
747 | first array, and so on. In general, the <CODE>i</CODE>-th element of the |
||
748 | <CODE>j</CODE>-th input array will be in position <CODE>in[i * istride + j * |
||
749 | idist]</CODE>. Note that, here, <CODE>i</CODE> refers to an index into the row-major |
||
750 | format for the multi-dimensional array, rather than an index in any |
||
751 | particular dimension. |
||
752 | |||
753 | |||
754 | <UL> |
||
755 | <LI><EM>In-place transforms</EM>: |
||
756 | |||
757 | <A NAME="IDX143"></A> |
||
758 | For plans created with the <CODE>FFTW_IN_PLACE</CODE> option, the transform is |
||
759 | computed in-place--the output is returned in the <CODE>in</CODE> array, using |
||
760 | the same strides, etcetera, as were used in the input. |
||
761 | </UL> |
||
762 | |||
763 | <LI> |
||
764 | |||
765 | <CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output array(s). |
||
766 | The format is the same as for the input array. |
||
767 | |||
768 | |||
769 | <UL> |
||
770 | <LI><EM>In-place transforms</EM>: |
||
771 | |||
772 | These parameters are ignored for plans created with the |
||
773 | <CODE>FFTW_IN_PLACE</CODE> option. |
||
774 | </UL> |
||
775 | |||
776 | </UL> |
||
777 | |||
778 | <P> |
||
779 | The function <CODE>fftwnd_one</CODE> transforms a single, contiguous input |
||
780 | array to a contiguous output array. By definition, the call |
||
781 | |||
782 | <PRE> |
||
783 | fftwnd_one(plan, in, out) |
||
784 | </PRE> |
||
785 | |||
786 | <P> |
||
787 | is equivalent to |
||
788 | |||
789 | <PRE> |
||
790 | fftwnd(plan, 1, in, 1, 1, out, 1, 1) |
||
791 | </PRE> |
||
792 | |||
793 | |||
794 | |||
795 | <H3><A NAME="SEC27">Destroying a Multi-dimensional Plan</A></H3> |
||
796 | |||
797 | |||
798 | <PRE> |
||
799 | #include <fftw.h> |
||
800 | |||
801 | void fftwnd_destroy_plan(fftwnd_plan plan); |
||
802 | </PRE> |
||
803 | |||
804 | <P> |
||
805 | <A NAME="IDX144"></A> |
||
806 | |||
807 | |||
808 | <P> |
||
809 | The function <CODE>fftwnd_destroy_plan</CODE> frees the plan <CODE>plan</CODE> |
||
810 | and releases all the memory associated with it. After destruction, |
||
811 | a plan is no longer valid. |
||
812 | |||
813 | |||
814 | |||
815 | |||
816 | <H3><A NAME="SEC28">What FFTWND Really Computes</A></H3> |
||
817 | <P> |
||
818 | <A NAME="IDX145"></A> |
||
819 | |||
820 | |||
821 | <P> |
||
822 | The conventions that we follow for the multi-dimensional transform are |
||
823 | analogous to those for the one-dimensional transform. In particular, the |
||
824 | forward transform has a negative sign in the exponent and neither the |
||
825 | forward nor the backward transforms will perform any normalization. |
||
826 | Computing the backward transform of the forward transform will multiply |
||
827 | the array by the product of its dimensions. The output is in-order, and |
||
828 | the zeroth element of the output is the amplitude of the zero frequency |
||
829 | component. |
||
830 | |||
831 | |||
832 | The Gods forbade using HTML to display mathematical formulas. Please |
||
833 | see the TeX or Postscript version of this manual for the proper |
||
834 | definition of the n-dimensional Fourier transform that FFTW |
||
835 | uses. For completeness, we include a bitmap of the TeX output below: |
||
836 | <P><center><IMG SRC="equation-3.gif" ALIGN="top"></center> |
||
837 | |||
838 | |||
839 | |||
840 | <H2><A NAME="SEC29">Real One-dimensional Transforms Reference</A></H2> |
||
841 | |||
842 | <P> |
||
843 | The one-dimensional real routines are generally prefixed with |
||
844 | <CODE>rfftw_</CODE>. <A NAME="DOCF4" HREF="fftw_foot.html#FOOT4">(4)</A> Programs using RFFTW |
||
845 | should be linked with <CODE>-lrfftw -lfftw -lm</CODE> on Unix systems, or with |
||
846 | the RFFTW, the FFTW, and the standard math libraries in general. |
||
847 | <A NAME="IDX146"></A> |
||
848 | <A NAME="IDX147"></A> |
||
849 | <A NAME="IDX148"></A> |
||
850 | |||
851 | |||
852 | |||
853 | |||
854 | <H3><A NAME="SEC30">Plan Creation for Real One-dimensional Transforms</A></H3> |
||
855 | |||
856 | |||
857 | <PRE> |
||
858 | #include <rfftw.h> |
||
859 | |||
860 | rfftw_plan rfftw_create_plan(int n, fftw_direction dir, int flags); |
||
861 | |||
862 | rfftw_plan rfftw_create_plan_specific(int n, fftw_direction dir, |
||
863 | int flags, fftw_real *in, int istride, |
||
864 | fftw_real *out, int ostride); |
||
865 | </PRE> |
||
866 | |||
867 | <P> |
||
868 | <A NAME="IDX149"></A> |
||
869 | <A NAME="IDX150"></A> |
||
870 | <A NAME="IDX151"></A> |
||
871 | |||
872 | |||
873 | <P> |
||
874 | The function <CODE>rfftw_create_plan</CODE> creates a plan, which is a data |
||
875 | structure containing all the information that <CODE>rfftw</CODE> needs in |
||
876 | order to compute the 1D real Fourier transform. You can create as many |
||
877 | plans as you need, but only one plan for a given array size is required |
||
878 | (a plan can be reused many times). |
||
879 | |||
880 | |||
881 | <P> |
||
882 | <CODE>rfftw_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> if, for |
||
883 | some reason, the plan can't be created. In the default installation, |
||
884 | this cannot happen, but it is possible to configure RFFTW in such a way |
||
885 | that some input sizes are forbidden, and RFFTW cannot create a plan. |
||
886 | |||
887 | |||
888 | <P> |
||
889 | The <CODE>rfftw_create_plan_specific</CODE> variant takes as additional |
||
890 | arguments specific input/output arrays and their strides. For the last |
||
891 | four arguments, you should pass the arrays and strides that you will |
||
892 | eventually be passing to <CODE>rfftw</CODE>. The resulting plans will be |
||
893 | optimized for those arrays and strides, although they may be used on |
||
894 | other arrays as well. Note: the contents of the in and out arrays are |
||
895 | <EM>destroyed</EM> by the specific planner (the initial contents are |
||
896 | ignored, so the arrays need not have been initialized). |
||
897 | See Section <A HREF="fftw_3.html#SEC20">Discussion on Specific Plans</A>, for a discussion on specific plans. |
||
898 | |||
899 | |||
900 | |||
901 | <H4>Arguments</H4> |
||
902 | |||
903 | <UL> |
||
904 | <LI> |
||
905 | |||
906 | <CODE>n</CODE> is the size of the transform. It can be |
||
907 | any positive integer. |
||
908 | |||
909 | |||
910 | <UL> |
||
911 | <LI> |
||
912 | |||
913 | RFFTW is best at handling sizes of the form |
||
914 | 2<SUP>a</SUP> 3<SUP>b</SUP> 5<SUP>c</SUP> 7<SUP>d</SUP> |
||
915 | 11<SUP>e</SUP> 13<SUP>f</SUP>, |
||
916 | where e+f is either 0 or |
||
917 | 1, and the other exponents are arbitrary. Other sizes are |
||
918 | computed by means of a slow, general-purpose routine (reducing to |
||
919 | O(n<sup>2</sup>) |
||
920 | performance for prime sizes). (It is possible to customize RFFTW for |
||
921 | different array sizes. See Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A>, for more |
||
922 | information.) Transforms whose sizes are powers of 2 are |
||
923 | especially fast. |
||
924 | </UL> |
||
925 | |||
926 | <LI> |
||
927 | |||
928 | <CODE>dir</CODE> is the direction of the desired transform, either |
||
929 | <CODE>FFTW_REAL_TO_COMPLEX</CODE> or <CODE>FFTW_COMPLEX_TO_REAL</CODE>, |
||
930 | corresponding to <CODE>FFTW_FORWARD</CODE> or <CODE>FFTW_BACKWARD</CODE>, |
||
931 | respectively. |
||
932 | <A NAME="IDX152"></A> |
||
933 | <A NAME="IDX153"></A> |
||
934 | |||
935 | <LI> |
||
936 | |||
937 | <A NAME="IDX154"></A> |
||
938 | <CODE>flags</CODE> is a boolean OR (<SAMP>`|'</SAMP>) of zero or more of the following: |
||
939 | |||
940 | <UL> |
||
941 | <LI> |
||
942 | |||
943 | <CODE>FFTW_MEASURE</CODE>: this flag tells RFFTW to find the optimal plan by |
||
944 | actually <EM>computing</EM> several FFTs and measuring their |
||
945 | execution time. Depending on the installation, this can take some |
||
946 | time. |
||
947 | |||
948 | <LI> |
||
949 | |||
950 | <CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable" |
||
951 | plan (for a RISC processor with many registers). If neither |
||
952 | <CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is |
||
953 | <CODE>FFTW_ESTIMATE</CODE>. |
||
954 | |||
955 | <LI> |
||
956 | |||
957 | <CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input |
||
958 | and output arrays will be distinct (this is the default). |
||
959 | |||
960 | <LI> |
||
961 | |||
962 | <CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want the output |
||
963 | in the input array. The algorithm used is not necessarily in place: |
||
964 | RFFTW is able to compute true in-place transforms only for small values |
||
965 | of <CODE>n</CODE>. If RFFTW is not able to compute the transform in-place, it |
||
966 | will allocate a temporary array (unless you provide one yourself), |
||
967 | compute the transform out of place, and copy the result back. |
||
968 | <EM>Warning: This option changes the meaning of some parameters of |
||
969 | <CODE>rfftw</CODE></EM> (see Section <A HREF="fftw_3.html#SEC31">Computing the Real One-dimensional Transform</A>). |
||
970 | |||
971 | The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>. |
||
972 | |||
973 | <LI> |
||
974 | |||
975 | <CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help |
||
976 | in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.) |
||
977 | This can greatly speed the creation of plans, especially with the |
||
978 | <CODE>FFTW_MEASURE</CODE> option. <CODE>FFTW_ESTIMATE</CODE> plans can also take |
||
979 | advantage of <CODE>wisdom</CODE> to produce a more optimal plan (based on past |
||
980 | measurements) than the estimation heuristic would normally |
||
981 | generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE> |
||
982 | will also be generated if the current transform size is not completely |
||
983 | understood by existing <CODE>wisdom</CODE>. |
||
984 | |||
985 | </UL> |
||
986 | |||
987 | <LI> |
||
988 | |||
989 | <CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for |
||
990 | <CODE>rfftw_create_plan_specific</CODE>): see corresponding arguments in the |
||
991 | description of <CODE>rfftw</CODE>. (See Section <A HREF="fftw_3.html#SEC31">Computing the Real One-dimensional Transform</A>.) In particular, the <CODE>out</CODE> and |
||
992 | <CODE>ostride</CODE> parameters have the same special meaning for |
||
993 | <CODE>FFTW_IN_PLACE</CODE> transforms as they have for <CODE>rfftw</CODE>. |
||
994 | |||
995 | </UL> |
||
996 | |||
997 | |||
998 | |||
999 | <H3><A NAME="SEC31">Computing the Real One-dimensional Transform</A></H3> |
||
1000 | |||
1001 | |||
1002 | <PRE> |
||
1003 | #include <rfftw.h> |
||
1004 | |||
1005 | void rfftw(rfftw_plan plan, int howmany, |
||
1006 | fftw_real *in, int istride, int idist, |
||
1007 | fftw_real *out, int ostride, int odist); |
||
1008 | |||
1009 | void rfftw_one(rfftw_plan plan, fftw_real *in, fftw_real *out); |
||
1010 | </PRE> |
||
1011 | |||
1012 | <P> |
||
1013 | <A NAME="IDX155"></A> |
||
1014 | <A NAME="IDX156"></A> |
||
1015 | |||
1016 | |||
1017 | <P> |
||
1018 | The function <CODE>rfftw</CODE> computes the Real One-dimensional Fourier |
||
1019 | Transform, using a plan created by <CODE>rfftw_create_plan</CODE> |
||
1020 | (see Section <A HREF="fftw_3.html#SEC30">Plan Creation for Real One-dimensional Transforms</A>). The function <CODE>rfftw_one</CODE> provides a simplified |
||
1021 | interface for the common case of single input array of stride 1. |
||
1022 | <A NAME="IDX157"></A> |
||
1023 | |||
1024 | |||
1025 | <P> |
||
1026 | <EM>Important:</EM> When invoked for an out-of-place, |
||
1027 | <CODE>FFTW_COMPLEX_TO_REAL</CODE> transform, the input array is overwritten |
||
1028 | with scratch values by these routines. The input array is not modified |
||
1029 | for <CODE>FFTW_REAL_TO_COMPLEX</CODE> transforms. |
||
1030 | |||
1031 | |||
1032 | |||
1033 | <H4>Arguments</H4> |
||
1034 | |||
1035 | <UL> |
||
1036 | <LI> |
||
1037 | |||
1038 | <CODE>plan</CODE> is the plan created by <CODE>rfftw_create_plan</CODE> |
||
1039 | (see Section <A HREF="fftw_3.html#SEC30">Plan Creation for Real One-dimensional Transforms</A>). |
||
1040 | |||
1041 | <LI> |
||
1042 | |||
1043 | <CODE>howmany</CODE> is the number of transforms <CODE>rfftw</CODE> will compute. |
||
1044 | It is faster to tell RFFTW to compute many transforms, instead of |
||
1045 | simply calling <CODE>rfftw</CODE> many times. |
||
1046 | |||
1047 | <LI> |
||
1048 | |||
1049 | <CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s). |
||
1050 | There are two cases. If the <CODE>plan</CODE> defines a |
||
1051 | <CODE>FFTW_REAL_TO_COMPLEX</CODE> transform, <CODE>in</CODE> is a real array. |
||
1052 | Otherwise, for <CODE>FFTW_COMPLEX_TO_REAL</CODE> transforms, <CODE>in</CODE> is a |
||
1053 | halfcomplex array <EM>whose contents will be destroyed</EM>. |
||
1054 | |||
1055 | <LI> |
||
1056 | |||
1057 | <CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output |
||
1058 | array(s), and have the same meaning as the corresponding parameters for |
||
1059 | the input array. |
||
1060 | |||
1061 | |||
1062 | <UL> |
||
1063 | <LI><EM>In-place transforms</EM>: |
||
1064 | |||
1065 | If the <CODE>plan</CODE> specifies an in-place transform, <CODE>ostride</CODE> and |
||
1066 | <CODE>odist</CODE> are always ignored. If <CODE>out</CODE> is <CODE>NULL</CODE>, |
||
1067 | <CODE>out</CODE> is ignored, too. Otherwise, <CODE>out</CODE> is interpreted as a |
||
1068 | pointer to an array of <CODE>n</CODE> complex numbers, that FFTW will use as |
||
1069 | temporary space to perform the in-place computation. <CODE>out</CODE> is used |
||
1070 | as scratch space and its contents destroyed. In this case, <CODE>out</CODE> |
||
1071 | must be an ordinary array whose elements are contiguous in memory (no |
||
1072 | striding). |
||
1073 | </UL> |
||
1074 | |||
1075 | </UL> |
||
1076 | |||
1077 | <P> |
||
1078 | The function <CODE>rfftw_one</CODE> transforms a single, contiguous input array |
||
1079 | to a contiguous output array. By definition, the call |
||
1080 | |||
1081 | <PRE> |
||
1082 | rfftw_one(plan, in, out) |
||
1083 | </PRE> |
||
1084 | |||
1085 | <P> |
||
1086 | is equivalent to |
||
1087 | |||
1088 | <PRE> |
||
1089 | rfftw(plan, 1, in, 1, 1, out, 1, 1) |
||
1090 | </PRE> |
||
1091 | |||
1092 | |||
1093 | |||
1094 | <H3><A NAME="SEC32">Destroying a Real One-dimensional Plan</A></H3> |
||
1095 | |||
1096 | |||
1097 | <PRE> |
||
1098 | #include <rfftw.h> |
||
1099 | |||
1100 | void rfftw_destroy_plan(rfftw_plan plan); |
||
1101 | </PRE> |
||
1102 | |||
1103 | <P> |
||
1104 | <A NAME="IDX158"></A> |
||
1105 | |||
1106 | |||
1107 | <P> |
||
1108 | The function <CODE>rfftw_destroy_plan</CODE> frees the plan <CODE>plan</CODE> and |
||
1109 | releases all the memory associated with it. After destruction, a plan |
||
1110 | is no longer valid. |
||
1111 | |||
1112 | |||
1113 | |||
1114 | |||
1115 | <H3><A NAME="SEC33">What RFFTW Really Computes</A></H3> |
||
1116 | <P> |
||
1117 | <A NAME="IDX159"></A> |
||
1118 | In this section, we define precisely what RFFTW computes. |
||
1119 | |||
1120 | |||
1121 | <P> |
||
1122 | The real to complex (<CODE>FFTW_REAL_TO_COMPLEX</CODE>) transform of a real |
||
1123 | array X of size n computes an hermitian array Y, |
||
1124 | where |
||
1125 | <center><IMG SRC="equation-1.gif" ALIGN="top"></center> |
||
1126 | (That Y is a hermitian array is not intended to be obvious, |
||
1127 | although the proof is easy.) The hermitian array Y is stored in |
||
1128 | halfcomplex order (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>). Currently, RFFTW provides no |
||
1129 | way to compute a real to complex transform with a positive sign in the |
||
1130 | exponent. |
||
1131 | |||
1132 | |||
1133 | <P> |
||
1134 | The complex to real (<CODE>FFTW_COMPLEX_TO_REAL</CODE>) transform of a hermitian |
||
1135 | array X of size n computes a real array Y, where |
||
1136 | <center><IMG SRC="equation-2.gif" ALIGN="top"></center> |
||
1137 | (That Y is a real array is not intended to be obvious, although |
||
1138 | the proof is easy.) The hermitian input array X is stored in |
||
1139 | halfcomplex order (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>). Currently, RFFTW provides no |
||
1140 | way to compute a complex to real transform with a negative sign in the |
||
1141 | exponent. |
||
1142 | |||
1143 | |||
1144 | <P> |
||
1145 | <A NAME="IDX160"></A> |
||
1146 | Like FFTW, RFFTW computes an unnormalized transform. In other words, |
||
1147 | applying the real to complex (forward) and then the complex to real |
||
1148 | (backward) transform will multiply the input by n. |
||
1149 | |||
1150 | |||
1151 | |||
1152 | |||
1153 | <H2><A NAME="SEC34">Real Multi-dimensional Transforms Reference</A></H2> |
||
1154 | <P> |
||
1155 | <A NAME="IDX161"></A> |
||
1156 | <A NAME="IDX162"></A> |
||
1157 | |||
1158 | |||
1159 | <P> |
||
1160 | The multi-dimensional real routines are generally prefixed with |
||
1161 | <CODE>rfftwnd_</CODE>. Programs using RFFTWND should be linked with |
||
1162 | <CODE>-lrfftw -lfftw -lm</CODE> on Unix systems, or with the FFTW, RFFTW, and |
||
1163 | standard math libraries in general. |
||
1164 | <A NAME="IDX163"></A> |
||
1165 | |||
1166 | |||
1167 | |||
1168 | |||
1169 | <H3><A NAME="SEC35">Plan Creation for Real Multi-dimensional Transforms</A></H3> |
||
1170 | |||
1171 | |||
1172 | <PRE> |
||
1173 | #include <rfftw.h> |
||
1174 | |||
1175 | rfftwnd_plan rfftwnd_create_plan(int rank, const int *n, |
||
1176 | fftw_direction dir, int flags); |
||
1177 | |||
1178 | rfftwnd_plan rfftw2d_create_plan(int nx, int ny, |
||
1179 | fftw_direction dir, int flags); |
||
1180 | |||
1181 | rfftwnd_plan rfftw3d_create_plan(int nx, int ny, int nz, |
||
1182 | fftw_direction dir, int flags); |
||
1183 | </PRE> |
||
1184 | |||
1185 | <P> |
||
1186 | <A NAME="IDX164"></A> |
||
1187 | <A NAME="IDX165"></A> |
||
1188 | <A NAME="IDX166"></A> |
||
1189 | <A NAME="IDX167"></A> |
||
1190 | <A NAME="IDX168"></A> |
||
1191 | |||
1192 | |||
1193 | <P> |
||
1194 | The function <CODE>rfftwnd_create_plan</CODE> creates a plan, which is a data |
||
1195 | structure containing all the information that <CODE>rfftwnd</CODE> needs in |
||
1196 | order to compute a multi-dimensional real Fourier transform. You can |
||
1197 | create as many plans as you need, but only one plan for a given array |
||
1198 | size is required (a plan can be reused many times). The functions |
||
1199 | <CODE>rfftw2d_create_plan</CODE> and <CODE>rfftw3d_create_plan</CODE> are optional, |
||
1200 | alternative interfaces to <CODE>rfftwnd_create_plan</CODE> for two and three |
||
1201 | dimensions, respectively. |
||
1202 | |||
1203 | |||
1204 | <P> |
||
1205 | <CODE>rfftwnd_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> if, for |
||
1206 | some reason, the plan can't be created. This can happen if the |
||
1207 | arguments are invalid in some way (e.g. if <CODE>rank</CODE> < 0). |
||
1208 | |||
1209 | |||
1210 | |||
1211 | <H4>Arguments</H4> |
||
1212 | |||
1213 | <UL> |
||
1214 | <LI> |
||
1215 | |||
1216 | <CODE>rank</CODE> is the dimensionality of the arrays to be transformed. It |
||
1217 | can be any non-negative integer. |
||
1218 | |||
1219 | <LI> |
||
1220 | |||
1221 | <CODE>n</CODE> is a pointer to an array of <CODE>rank</CODE> integers, giving the |
||
1222 | size of each dimension of the arrays to be transformed. Note that these |
||
1223 | are always the dimensions of the <EM>real</EM> arrays; the complex arrays |
||
1224 | have different dimensions (see Section <A HREF="fftw_3.html#SEC37">Array Dimensions for Real Multi-dimensional Transforms</A>). These sizes, which must be positive |
||
1225 | integers, correspond to the dimensions of row-major |
||
1226 | arrays--i.e. <CODE>n[0]</CODE> is the size of the dimension whose indices |
||
1227 | vary most slowly, and so on. (See Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>, for |
||
1228 | more information.) |
||
1229 | |||
1230 | <UL> |
||
1231 | <LI> |
||
1232 | |||
1233 | See Section <A HREF="fftw_3.html#SEC30">Plan Creation for Real One-dimensional Transforms</A>, |
||
1234 | for more information regarding optimal array sizes. |
||
1235 | </UL> |
||
1236 | |||
1237 | <LI> |
||
1238 | |||
1239 | <CODE>nx</CODE> and <CODE>ny</CODE> in <CODE>rfftw2d_create_plan</CODE> are positive |
||
1240 | integers specifying the dimensions of the rank 2 array to be |
||
1241 | transformed. i.e. they specify that the transform will operate on |
||
1242 | <CODE>nx x ny</CODE> arrays in row-major order, where <CODE>nx</CODE> is the number |
||
1243 | of rows and <CODE>ny</CODE> is the number of columns. |
||
1244 | |||
1245 | <LI> |
||
1246 | |||
1247 | <CODE>nx</CODE>, <CODE>ny</CODE> and <CODE>nz</CODE> in <CODE>rfftw3d_create_plan</CODE> are |
||
1248 | positive integers specifying the dimensions of the rank 3 array to be |
||
1249 | transformed. i.e. they specify that the transform will operate on |
||
1250 | <CODE>nx x ny x nz</CODE> arrays in row-major order. |
||
1251 | |||
1252 | <LI> |
||
1253 | |||
1254 | <CODE>dir</CODE> is the direction of the desired transform, either |
||
1255 | <CODE>FFTW_REAL_TO_COMPLEX</CODE> or <CODE>FFTW_COMPLEX_TO_REAL</CODE>, |
||
1256 | corresponding to <CODE>FFTW_FORWARD</CODE> or <CODE>FFTW_BACKWARD</CODE>, |
||
1257 | respectively. |
||
1258 | |||
1259 | <LI> |
||
1260 | |||
1261 | <A NAME="IDX169"></A> |
||
1262 | <CODE>flags</CODE> is a boolean OR (<SAMP>`|'</SAMP>) of zero or more of the following: |
||
1263 | |||
1264 | <UL> |
||
1265 | <LI> |
||
1266 | |||
1267 | <CODE>FFTW_MEASURE</CODE>: this flag tells FFTW to find the optimal plan by |
||
1268 | actually <EM>computing</EM> several FFTs and measuring their execution |
||
1269 | time. |
||
1270 | |||
1271 | <LI> |
||
1272 | |||
1273 | <CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable" |
||
1274 | plan (for a RISC processor with many registers). If neither |
||
1275 | <CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is |
||
1276 | <CODE>FFTW_ESTIMATE</CODE>. |
||
1277 | |||
1278 | <LI> |
||
1279 | |||
1280 | <CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input |
||
1281 | and output arrays will be distinct (this is the default). |
||
1282 | |||
1283 | <LI> |
||
1284 | |||
1285 | <A NAME="IDX170"></A> |
||
1286 | <CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want to perform |
||
1287 | the transform in-place. (Unlike the one-dimensional transform, this |
||
1288 | "really" performs the transform in-place.) Note that, if you want to |
||
1289 | perform in-place transforms, you <EM>must</EM> use a plan created with |
||
1290 | this option. The use of this option has important implications for the |
||
1291 | size of the input/output array (see Section <A HREF="fftw_3.html#SEC36">Computing the Real Multi-dimensional Transform</A>). |
||
1292 | |||
1293 | The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>. |
||
1294 | |||
1295 | <LI> |
||
1296 | |||
1297 | <A NAME="IDX171"></A> |
||
1298 | <CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help |
||
1299 | in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.) This can greatly |
||
1300 | speed the creation of plans, especially with the <CODE>FFTW_MEASURE</CODE> |
||
1301 | option. <CODE>FFTW_ESTIMATE</CODE> plans can also take advantage of |
||
1302 | <CODE>wisdom</CODE> to produce a more optimal plan (based on past |
||
1303 | measurements) than the estimation heuristic would normally |
||
1304 | generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE> |
||
1305 | will also be generated if the current transform size is not completely |
||
1306 | understood by existing <CODE>wisdom</CODE>. Note that the same <CODE>wisdom</CODE> |
||
1307 | is shared between one-dimensional and multi-dimensional transforms. |
||
1308 | |||
1309 | </UL> |
||
1310 | |||
1311 | </UL> |
||
1312 | |||
1313 | |||
1314 | |||
1315 | <H3><A NAME="SEC36">Computing the Real Multi-dimensional Transform</A></H3> |
||
1316 | |||
1317 | |||
1318 | <PRE> |
||
1319 | #include <rfftw.h> |
||
1320 | |||
1321 | void rfftwnd_real_to_complex(rfftwnd_plan plan, int howmany, |
||
1322 | fftw_real *in, int istride, int idist, |
||
1323 | fftw_complex *out, int ostride, int odist); |
||
1324 | void rfftwnd_complex_to_real(rfftwnd_plan plan, int howmany, |
||
1325 | fftw_complex *in, int istride, int idist, |
||
1326 | fftw_real *out, int ostride, int odist); |
||
1327 | |||
1328 | void rfftwnd_one_real_to_complex(rfftwnd_plan p, fftw_real *in, |
||
1329 | fftw_complex *out); |
||
1330 | void rfftwnd_one_complex_to_real(rfftwnd_plan p, fftw_complex *in, |
||
1331 | fftw_real *out); |
||
1332 | </PRE> |
||
1333 | |||
1334 | <P> |
||
1335 | <A NAME="IDX172"></A> |
||
1336 | <A NAME="IDX173"></A> |
||
1337 | <A NAME="IDX174"></A> |
||
1338 | <A NAME="IDX175"></A> |
||
1339 | |||
1340 | |||
1341 | <P> |
||
1342 | These functions compute the real multi-dimensional Fourier Transform, |
||
1343 | using a plan created by <CODE>rfftwnd_create_plan</CODE> |
||
1344 | (see Section <A HREF="fftw_3.html#SEC35">Plan Creation for Real Multi-dimensional Transforms</A>). (Note that the plan determines the rank and dimensions of |
||
1345 | the array to be transformed.) The <SAMP>`<CODE>rfftwnd_one_</CODE>'</SAMP> functions |
||
1346 | provide a simplified interface for the common case of single input array |
||
1347 | of stride 1. Unlike other transform routines in FFTW, we here use |
||
1348 | separate functions for the two directions of the transform in order to |
||
1349 | correctly express the datatypes of the parameters. |
||
1350 | |||
1351 | |||
1352 | <P> |
||
1353 | <EM>Important:</EM> When invoked for an out-of-place, |
||
1354 | <CODE>FFTW_COMPLEX_TO_REAL</CODE> transform with <CODE>rank > 1</CODE>, the input |
||
1355 | array is overwritten with scratch values by these routines. The input |
||
1356 | array is not modified for <CODE>FFTW_REAL_TO_COMPLEX</CODE> transforms or for |
||
1357 | <CODE>FFTW_COMPLEX_TO_REAL</CODE> with <CODE>rank == 1</CODE>. |
||
1358 | |||
1359 | |||
1360 | |||
1361 | <H4>Arguments</H4> |
||
1362 | |||
1363 | <UL> |
||
1364 | <LI> |
||
1365 | |||
1366 | <CODE>plan</CODE> is the plan created by <CODE>rfftwnd_create_plan</CODE>. |
||
1367 | (see Section <A HREF="fftw_3.html#SEC35">Plan Creation for Real Multi-dimensional Transforms</A>). In the case of two and three-dimensional transforms, it |
||
1368 | could also have been created by <CODE>rfftw2d_create_plan</CODE> or |
||
1369 | <CODE>rfftw3d_create_plan</CODE>, respectively. |
||
1370 | |||
1371 | <CODE>FFTW_REAL_TO_COMPLEX</CODE> plans must be used with the |
||
1372 | <SAMP>`<CODE>real_to_complex</CODE>'</SAMP> functions, and <CODE>FFTW_COMPLEX_TO_REAL</CODE> |
||
1373 | plans must be used with the <SAMP>`<CODE>complex_to_real</CODE>'</SAMP> functions. It |
||
1374 | is an error to mismatch the plan direction and the transform function. |
||
1375 | |||
1376 | <LI> |
||
1377 | |||
1378 | <CODE>howmany</CODE> is the number of transforms to be computed. |
||
1379 | |||
1380 | <LI> |
||
1381 | |||
1382 | <A NAME="IDX176"></A> |
||
1383 | <CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s). |
||
1384 | There are <CODE>howmany</CODE> input arrays; the first one is pointed to by |
||
1385 | <CODE>in</CODE>, the second one is pointed to by <CODE>in + idist</CODE>, and so on, |
||
1386 | up to <CODE>in + (howmany - 1) * idist</CODE>. Each input array is stored in |
||
1387 | row-major format (see Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>), and is not |
||
1388 | necessarily contiguous in memory. Specifically, <CODE>in[0]</CODE> is the |
||
1389 | first element of the first array, <CODE>in[istride]</CODE> is the second |
||
1390 | element of the first array, and so on. In general, the <CODE>i</CODE>-th |
||
1391 | element of the <CODE>j</CODE>-th input array will be in position <CODE>in[i * |
||
1392 | istride + j * idist]</CODE>. Note that, here, <CODE>i</CODE> refers to an index into |
||
1393 | the row-major format for the multi-dimensional array, rather than an |
||
1394 | index in any particular dimension. |
||
1395 | |||
1396 | The dimensions of the arrays are different for real and complex data, |
||
1397 | and are discussed in more detail below (see Section <A HREF="fftw_3.html#SEC37">Array Dimensions for Real Multi-dimensional Transforms</A>). |
||
1398 | |||
1399 | |||
1400 | <UL> |
||
1401 | <LI><EM>In-place transforms</EM>: |
||
1402 | |||
1403 | For plans created with the <CODE>FFTW_IN_PLACE</CODE> option, the transform is |
||
1404 | computed in-place--the output is returned in the <CODE>in</CODE> array. The |
||
1405 | meaning of the <CODE>stride</CODE> and <CODE>dist</CODE> parameters in this case is |
||
1406 | subtle and is discussed below (see Section <A HREF="fftw_3.html#SEC38">Strides in In-place RFFTWND</A>). |
||
1407 | </UL> |
||
1408 | |||
1409 | <LI> |
||
1410 | |||
1411 | <CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output |
||
1412 | array(s). The format is the same as that for the input array. See |
||
1413 | below for a discussion of the dimensions of the output array for real |
||
1414 | and complex data. |
||
1415 | |||
1416 | |||
1417 | <UL> |
||
1418 | <LI><EM>In-place transforms</EM>: |
||
1419 | |||
1420 | These parameters are ignored for plans created with the |
||
1421 | <CODE>FFTW_IN_PLACE</CODE> option. |
||
1422 | </UL> |
||
1423 | |||
1424 | </UL> |
||
1425 | |||
1426 | <P> |
||
1427 | The function <CODE>rfftwnd_one</CODE> transforms a single, contiguous input |
||
1428 | array to a contiguous output array. By definition, the call |
||
1429 | |||
1430 | <PRE> |
||
1431 | rfftwnd_one_...(plan, in, out) |
||
1432 | </PRE> |
||
1433 | |||
1434 | <P> |
||
1435 | is equivalent to |
||
1436 | |||
1437 | <PRE> |
||
1438 | rfftwnd_...(plan, 1, in, 1, 1, out, 1, 1) |
||
1439 | </PRE> |
||
1440 | |||
1441 | |||
1442 | |||
1443 | <H3><A NAME="SEC37">Array Dimensions for Real Multi-dimensional Transforms</A></H3> |
||
1444 | |||
1445 | <P> |
||
1446 | <A NAME="IDX177"></A> |
||
1447 | The output of a multi-dimensional transform of real data contains |
||
1448 | symmetries that, in principle, make half of the outputs redundant |
||
1449 | (see Section <A HREF="fftw_3.html#SEC40">What RFFTWND Really Computes</A>). In practice, it is not |
||
1450 | possible to entirely realize these savings in an efficient and |
||
1451 | understandable format. Instead, the output of the rfftwnd transforms is |
||
1452 | <EM>slightly</EM> over half of the output of the corresponding complex |
||
1453 | transform. We do not "pack" the data in any way, but store it as an |
||
1454 | ordinary array of <CODE>fftw_complex</CODE> values. In fact, this data is |
||
1455 | simply a subsection of what would be the array in the corresponding |
||
1456 | complex transform. |
||
1457 | |||
1458 | |||
1459 | <P> |
||
1460 | Specifically, for a real transform of dimensions |
||
1461 | n<sub>1</sub> x n<sub>2</sub> x ... x n<sub>d</sub>, |
||
1462 | the complex data is an |
||
1463 | n<sub>1</sub> x n<sub>2</sub> x ... x (n<sub>d</sub>/2+1) |
||
1464 | array of <CODE>fftw_complex</CODE> values in row-major order (with the |
||
1465 | division rounded down). That is, we only store the lower half (plus one |
||
1466 | element) of the last dimension of the data from the ordinary complex |
||
1467 | transform. (We could have instead taken half of any other dimension, |
||
1468 | but implementation turns out to be simpler if the last, contiguous, |
||
1469 | dimension is used.) |
||
1470 | |||
1471 | |||
1472 | <P> |
||
1473 | <A NAME="IDX178"></A> |
||
1474 | <A NAME="IDX179"></A> |
||
1475 | Since the complex data is slightly larger than the real data, some |
||
1476 | complications arise for in-place transforms. In this case, the final |
||
1477 | dimension of the real data must be padded with extra values to |
||
1478 | accommodate the size of the complex data--two extra if the last |
||
1479 | dimension is even and one if it is odd. That is, the last dimension of |
||
1480 | the real data must physically contain |
||
1481 | 2 * (n<sub>d</sub>/2+1) |
||
1482 | <CODE>fftw_real</CODE> values (exactly enough to hold the complex data). |
||
1483 | This physical array size does not, however, change the <EM>logical</EM> |
||
1484 | array size--only |
||
1485 | n<sub>d</sub> |
||
1486 | values are actually stored in the last dimension, and |
||
1487 | n<sub>d</sub> |
||
1488 | is the last dimension passed to <CODE>rfftwnd_create_plan</CODE>. |
||
1489 | |||
1490 | |||
1491 | |||
1492 | |||
1493 | <H3><A NAME="SEC38">Strides in In-place RFFTWND</A></H3> |
||
1494 | |||
1495 | <P> |
||
1496 | <A NAME="IDX180"></A> |
||
1497 | <A NAME="IDX181"></A> |
||
1498 | The fact that the input and output datatypes are different for rfftwnd |
||
1499 | complicates the meaning of the <CODE>stride</CODE> and <CODE>dist</CODE> parameters |
||
1500 | of in-place transforms--are they in units of <CODE>fftw_real</CODE> or |
||
1501 | <CODE>fftw_complex</CODE> elements? When reading the input, they are |
||
1502 | interpreted in units of the datatype of the input data. When writing |
||
1503 | the output, the <CODE>istride</CODE> and <CODE>idist</CODE> are translated to the |
||
1504 | output datatype's "units" in one of two ways, corresponding to the two |
||
1505 | most common situations in which <CODE>stride</CODE> and <CODE>dist</CODE> parameters |
||
1506 | are useful. Below, we refer to these "translated" parameters as |
||
1507 | <CODE>ostride_t</CODE> and <CODE>odist_t</CODE>. (Note that these are computed |
||
1508 | internally by rfftwnd; the actual <CODE>ostride</CODE> and <CODE>odist</CODE> |
||
1509 | parameters are ignored for in-place transforms.) |
||
1510 | |||
1511 | |||
1512 | <P> |
||
1513 | First, there is the case where you are transforming a number of |
||
1514 | contiguous arrays located one after another in memory. In this |
||
1515 | situation, <CODE>istride</CODE> is <CODE>1</CODE> and <CODE>idist</CODE> is the product of |
||
1516 | the physical dimensions of the array. <CODE>ostride_t</CODE> and |
||
1517 | <CODE>odist_t</CODE> are then chosen so that the output arrays are contiguous |
||
1518 | and lie on top of the input arrays. <CODE>ostride_t</CODE> is therefore |
||
1519 | <CODE>1</CODE>. For a real-to-complex transform, <CODE>odist_t</CODE> is |
||
1520 | <CODE>idist/2</CODE>; for a complex-to-real transform, <CODE>odist_t</CODE> is |
||
1521 | <CODE>idist*2</CODE>. |
||
1522 | |||
1523 | |||
1524 | <P> |
||
1525 | The second case is when you have an array in which each element has |
||
1526 | <CODE>nc</CODE> components (e.g. a structure with <CODE>nc</CODE> numeric fields), |
||
1527 | and you want to transform all of the components at once. Here, |
||
1528 | <CODE>istride</CODE> is <CODE>nc</CODE> and <CODE>idist</CODE> is <CODE>1</CODE>. For this |
||
1529 | case, it is natural to want the output to also have <CODE>nc</CODE> |
||
1530 | consecutive components, now of the output data type; this is exactly |
||
1531 | what rfftwnd does. Specifically, it uses an <CODE>ostride_t</CODE> equal to |
||
1532 | <CODE>istride</CODE>, and an <CODE>odist_t</CODE> of <CODE>1</CODE>. (Astute readers will |
||
1533 | realize that some extra buffer space is required in order to perform |
||
1534 | such a transform; this is handled automatically by rfftwnd.) |
||
1535 | |||
1536 | |||
1537 | <P> |
||
1538 | The general rule is as follows. <CODE>ostride_t</CODE> equals <CODE>istride</CODE>. |
||
1539 | If <CODE>idist</CODE> is <CODE>1</CODE>, then <CODE>odist_t</CODE> is <CODE>1</CODE>. |
||
1540 | Otherwise, for a real-to-complex transform <CODE>odist_t</CODE> is |
||
1541 | <CODE>idist/2</CODE> and for a complex-to-real transform <CODE>odist_t</CODE> is |
||
1542 | <CODE>idist*2</CODE>. |
||
1543 | |||
1544 | |||
1545 | |||
1546 | |||
1547 | <H3><A NAME="SEC39">Destroying a Multi-dimensional Plan</A></H3> |
||
1548 | |||
1549 | |||
1550 | <PRE> |
||
1551 | #include <rfftw.h> |
||
1552 | |||
1553 | void rfftwnd_destroy_plan(rfftwnd_plan plan); |
||
1554 | </PRE> |
||
1555 | |||
1556 | <P> |
||
1557 | <A NAME="IDX182"></A> |
||
1558 | |||
1559 | |||
1560 | <P> |
||
1561 | The function <CODE>rfftwnd_destroy_plan</CODE> frees the plan <CODE>plan</CODE> |
||
1562 | and releases all the memory associated with it. After destruction, |
||
1563 | a plan is no longer valid. |
||
1564 | |||
1565 | |||
1566 | |||
1567 | |||
1568 | <H3><A NAME="SEC40">What RFFTWND Really Computes</A></H3> |
||
1569 | <P> |
||
1570 | <A NAME="IDX183"></A> |
||
1571 | |||
1572 | |||
1573 | <P> |
||
1574 | The conventions that we follow for the real multi-dimensional transform |
||
1575 | are analogous to those for the complex multi-dimensional transform. In |
||
1576 | particular, the forward transform has a negative sign in the exponent |
||
1577 | and neither the forward nor the backward transforms will perform any |
||
1578 | normalization. Computing the backward transform of the forward |
||
1579 | transform will multiply the array by the product of its dimensions (that |
||
1580 | is, the logical dimensions of the real data). The forward transform is |
||
1581 | real-to-complex and the backward transform is complex-to-real. |
||
1582 | |||
1583 | |||
1584 | <P> |
||
1585 | <A NAME="IDX184"></A> |
||
1586 | <A NAME="IDX185"></A> |
||
1587 | The Gods forbade using HTML to display mathematical formulas. Please |
||
1588 | see the TeX or Postscript version of this manual for the proper |
||
1589 | definition of the n-dimensional real Fourier transform that RFFTW |
||
1590 | uses. For completeness, we include a bitmap of the TeX output below: |
||
1591 | <P><center><IMG SRC="equation-4.gif" ALIGN="top"></center> |
||
1592 | |||
1593 | |||
1594 | |||
1595 | |||
1596 | <H2><A NAME="SEC41">Wisdom Reference</A></H2> |
||
1597 | |||
1598 | <P> |
||
1599 | <A NAME="IDX186"></A> |
||
1600 | |||
1601 | |||
1602 | <H3><A NAME="SEC42">Exporting Wisdom</A></H3> |
||
1603 | |||
1604 | |||
1605 | <PRE> |
||
1606 | #include <fftw.h> |
||
1607 | |||
1608 | void fftw_export_wisdom(void (*emitter)(char c, void *), void *data); |
||
1609 | void fftw_export_wisdom_to_file(FILE *output_file); |
||
1610 | char *fftw_export_wisdom_to_string(void); |
||
1611 | </PRE> |
||
1612 | |||
1613 | <P> |
||
1614 | <A NAME="IDX187"></A> |
||
1615 | <A NAME="IDX188"></A> |
||
1616 | <A NAME="IDX189"></A> |
||
1617 | |||
1618 | |||
1619 | <P> |
||
1620 | These functions allow you to export all currently accumulated |
||
1621 | <CODE>wisdom</CODE> in a form from which it can be later imported and |
||
1622 | restored, even during a separate run of the program. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.) The current store of <CODE>wisdom</CODE> is not |
||
1623 | affected by calling any of these routines. |
||
1624 | |||
1625 | |||
1626 | <P> |
||
1627 | <CODE>fftw_export_wisdom</CODE> exports the <CODE>wisdom</CODE> to any output |
||
1628 | medium, as specified by the callback function |
||
1629 | <CODE>emitter</CODE>. <CODE>emitter</CODE> is a <CODE>putc</CODE>-like function that |
||
1630 | writes the character <CODE>c</CODE> to some output; its second parameter is |
||
1631 | the <CODE>data</CODE> pointer passed to <CODE>fftw_export_wisdom</CODE>. For |
||
1632 | convenience, the following two "wrapper" routines are provided: |
||
1633 | |||
1634 | |||
1635 | <P> |
||
1636 | <CODE>fftw_export_wisdom_to_file</CODE> writes the <CODE>wisdom</CODE> to the |
||
1637 | current position in <CODE>output_file</CODE>, which should be open with write |
||
1638 | permission. Upon exit, the file remains open and is positioned at the |
||
1639 | end of the <CODE>wisdom</CODE> data. |
||
1640 | |||
1641 | |||
1642 | <P> |
||
1643 | <CODE>fftw_export_wisdom_to_string</CODE> returns a pointer to a |
||
1644 | <CODE>NULL</CODE>-terminated string holding the <CODE>wisdom</CODE> data. This |
||
1645 | string is dynamically allocated, and it is the responsibility of the |
||
1646 | caller to deallocate it with <CODE>fftw_free</CODE> when it is no longer |
||
1647 | needed. |
||
1648 | |||
1649 | |||
1650 | <P> |
||
1651 | All of these routines export the wisdom in the same format, which we |
||
1652 | will not document here except to say that it is LISP-like ASCII text |
||
1653 | that is insensitive to white space. |
||
1654 | |||
1655 | |||
1656 | |||
1657 | |||
1658 | <H3><A NAME="SEC43">Importing Wisdom</A></H3> |
||
1659 | |||
1660 | |||
1661 | <PRE> |
||
1662 | #include <fftw.h> |
||
1663 | |||
1664 | fftw_status fftw_import_wisdom(int (*get_input)(void *), void *data); |
||
1665 | fftw_status fftw_import_wisdom_from_file(FILE *input_file); |
||
1666 | fftw_status fftw_import_wisdom_from_string(const char *input_string); |
||
1667 | </PRE> |
||
1668 | |||
1669 | <P> |
||
1670 | <A NAME="IDX190"></A> |
||
1671 | <A NAME="IDX191"></A> |
||
1672 | <A NAME="IDX192"></A> |
||
1673 | |||
1674 | |||
1675 | <P> |
||
1676 | These functions import <CODE>wisdom</CODE> into a program from data stored by |
||
1677 | the <CODE>fftw_export_wisdom</CODE> functions above. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.) |
||
1678 | The imported <CODE>wisdom</CODE> supplements rather than replaces any |
||
1679 | <CODE>wisdom</CODE> already accumulated by the running program (except when |
||
1680 | there is conflicting <CODE>wisdom</CODE>, in which case the existing wisdom is |
||
1681 | replaced). |
||
1682 | |||
1683 | |||
1684 | <P> |
||
1685 | <CODE>fftw_import_wisdom</CODE> imports <CODE>wisdom</CODE> from any input medium, |
||
1686 | as specified by the callback function <CODE>get_input</CODE>. <CODE>get_input</CODE> |
||
1687 | is a <CODE>getc</CODE>-like function that returns the next character in the |
||
1688 | input; its parameter is the <CODE>data</CODE> pointer passed to |
||
1689 | <CODE>fftw_import_wisdom</CODE>. If the end of the input data is reached |
||
1690 | (which should never happen for valid data), it may return either |
||
1691 | <CODE>NULL</CODE> (ASCII 0) or <CODE>EOF</CODE> (as defined in <CODE><stdio.h></CODE>). |
||
1692 | For convenience, the following two "wrapper" routines are provided: |
||
1693 | |||
1694 | |||
1695 | <P> |
||
1696 | <CODE>fftw_import_wisdom_from_file</CODE> reads <CODE>wisdom</CODE> from the |
||
1697 | current position in <CODE>input_file</CODE>, which should be open with read |
||
1698 | permission. Upon exit, the file remains open and is positioned at the |
||
1699 | end of the <CODE>wisdom</CODE> data. |
||
1700 | |||
1701 | |||
1702 | <P> |
||
1703 | <CODE>fftw_import_wisdom_from_string</CODE> reads <CODE>wisdom</CODE> from the |
||
1704 | <CODE>NULL</CODE>-terminated string <CODE>input_string</CODE>. |
||
1705 | |||
1706 | |||
1707 | <P> |
||
1708 | The return value of these routines is <CODE>FFTW_SUCCESS</CODE> if the wisdom |
||
1709 | was read successfully, and <CODE>FFTW_FAILURE</CODE> otherwise. Note that, in |
||
1710 | all of these functions, any data in the input stream past the end of the |
||
1711 | <CODE>wisdom</CODE> data is simply ignored (it is not even read if the |
||
1712 | <CODE>wisdom</CODE> data is well-formed). |
||
1713 | |||
1714 | |||
1715 | |||
1716 | |||
1717 | <H3><A NAME="SEC44">Forgetting Wisdom</A></H3> |
||
1718 | |||
1719 | |||
1720 | <PRE> |
||
1721 | #include <fftw.h> |
||
1722 | |||
1723 | void fftw_forget_wisdom(void); |
||
1724 | </PRE> |
||
1725 | |||
1726 | <P> |
||
1727 | <A NAME="IDX193"></A> |
||
1728 | |||
1729 | |||
1730 | <P> |
||
1731 | Calling <CODE>fftw_forget_wisdom</CODE> causes all accumulated <CODE>wisdom</CODE> |
||
1732 | to be discarded and its associated memory to be freed. (New |
||
1733 | <CODE>wisdom</CODE> can still be gathered subsequently, however.) |
||
1734 | |||
1735 | |||
1736 | |||
1737 | |||
1738 | <H2><A NAME="SEC45">Memory Allocator Reference</A></H2> |
||
1739 | |||
1740 | |||
1741 | <PRE> |
||
1742 | #include <fftw.h> |
||
1743 | |||
1744 | void *(*fftw_malloc_hook) (size_t n); |
||
1745 | void (*fftw_free_hook) (void *p); |
||
1746 | </PRE> |
||
1747 | |||
1748 | <P> |
||
1749 | <A NAME="IDX194"></A> |
||
1750 | <A NAME="IDX195"></A> |
||
1751 | <A NAME="IDX196"></A> |
||
1752 | <A NAME="IDX197"></A> |
||
1753 | |||
1754 | |||
1755 | <P> |
||
1756 | Whenever it has to allocate and release memory, FFTW ordinarily calls |
||
1757 | <CODE>malloc</CODE> and <CODE>free</CODE>. |
||
1758 | If <CODE>malloc</CODE> fails, FFTW prints an error message and exits. This |
||
1759 | behavior may be undesirable in some applications. Also, special |
||
1760 | memory-handling functions may be necessary in certain |
||
1761 | environments. Consequently, FFTW provides means by which you can install |
||
1762 | your own memory allocator and take whatever error-correcting action you |
||
1763 | find appropriate. The variables <CODE>fftw_malloc_hook</CODE> and |
||
1764 | <CODE>fftw_free_hook</CODE> are pointers to functions, and they are normally |
||
1765 | <CODE>NULL</CODE>. If you set those variables to point to other functions, |
||
1766 | then FFTW will use your routines instead of <CODE>malloc</CODE> and |
||
1767 | <CODE>free</CODE>. <CODE>fftw_malloc_hook</CODE> must point to a <CODE>malloc</CODE>-like |
||
1768 | function, and <CODE>fftw_free_hook</CODE> must point to a <CODE>free</CODE>-like |
||
1769 | function. |
||
1770 | |||
1771 | |||
1772 | |||
1773 | |||
1774 | <H2><A NAME="SEC46">Thread safety</A></H2> |
||
1775 | |||
1776 | <P> |
||
1777 | <A NAME="IDX198"></A> |
||
1778 | <A NAME="IDX199"></A> |
||
1779 | Users writing multi-threaded programs must concern themselves with the |
||
1780 | <EM>thread safety</EM> of the libraries they use--that is, whether it is |
||
1781 | safe to call routines in parallel from multiple threads. FFTW can be |
||
1782 | used in such an environment, but some care must be taken because certain |
||
1783 | parts of FFTW use private global variables to share data between calls. |
||
1784 | In particular, the plan-creation functions share trigonometric tables |
||
1785 | and accumulated <CODE>wisdom</CODE>. (Users should note that these comments |
||
1786 | only apply to programs using shared-memory threads. Parallelism using |
||
1787 | MPI or forked processes involves a separate address-space and global |
||
1788 | variables for each process, and is not susceptible to problems of this |
||
1789 | sort.) |
||
1790 | |||
1791 | |||
1792 | <P> |
||
1793 | The central restriction of FFTW is that it is not safe to create |
||
1794 | multiple plans in parallel. You must either create all of your plans |
||
1795 | from a single thread, or instead use a semaphore, mutex, or other |
||
1796 | mechanism to ensure that different threads don't attempt to create plans |
||
1797 | at the same time. The same restriction also holds for destruction of |
||
1798 | plans and importing/forgetting <CODE>wisdom</CODE>. Once created, a plan may |
||
1799 | safely be used in any thread. |
||
1800 | |||
1801 | |||
1802 | <P> |
||
1803 | The actual transform routines in FFTW (<CODE>fftw_one</CODE>, etcetera) are |
||
1804 | re-entrant and thread-safe, so it is fine to call them simultaneously |
||
1805 | from multiple threads. Another question arises, however--is it safe to |
||
1806 | use the <EM>same plan</EM> for multiple transforms in parallel? (It would |
||
1807 | be unsafe if, for example, the plan were modified in some way by the |
||
1808 | transform.) We address this question by defining an additional planner |
||
1809 | flag, <CODE>FFTW_THREADSAFE</CODE>. |
||
1810 | <A NAME="IDX200"></A> |
||
1811 | When included in the flags for any of the plan-creation routines, |
||
1812 | <CODE>FFTW_THREADSAFE</CODE> guarantees that the resulting plan will be |
||
1813 | read-only and safe to use in parallel by multiple threads. |
||
1814 | |||
1815 | |||
1816 | <P><HR><P> |
||
1817 | Go to the <A HREF="fftw_1.html">first</A>, <A HREF="fftw_2.html">previous</A>, <A HREF="fftw_4.html">next</A>, <A HREF="fftw_10.html">last</A> section, <A HREF="fftw_toc.html">table of contents</A>. |
||
1818 | </BODY> |
||
1819 | </HTML> |