Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
2 | pj | 1 | \comment This is the source for the FFTW FAQ list, in |
2 | \comment the Bizarre Format With No Name. It is turned into Lout |
||
3 | \comment input, HTML, plain ASCII and an Info document by a Perl script. |
||
4 | \comment |
||
5 | \comment The format and scripts come from the Linux FAQ, by |
||
6 | \comment Ian Jackson. |
||
7 | \set brieftitle FFTW FAQ |
||
8 | \set author <A href="http://theory.lcs.mit.edu/~fftw/">Matteo Frigo and Steven G. Johnson</A> / <A href="mailto:fftw@theory.lcs.mit.edu">fftw@theory.lcs.mit.edu</A> |
||
9 | \set authormail fftw@theory.lcs.mit.edu |
||
10 | \set title FFTW Frequently Asked Questions with Answers |
||
11 | \set copyholder Massachusetts Institute of Technology |
||
12 | \call-html startup html.refs |
||
13 | \copyto ASCII |
||
14 | FFTW FREQUENTLY ASKED QUESTIONS WITH ANSWERS |
||
15 | `date '+%d %h %Y'` |
||
16 | Matteo Frigo |
||
17 | Steven G. Johnson |
||
18 | <fftw@theory.lcs.mit.edu> |
||
19 | |||
20 | \endcopy |
||
21 | \copyto INFO |
||
22 | START-INFO-DIR-ENTRY |
||
23 | * FFTW FAQ: (fftw-faq). FFTW Frequently Asked Questions with Answers. |
||
24 | END-INFO-DIR-ENTRY |
||
25 | |||
26 | |||
27 | File: $prefix.info, Node: Top, Next: Question 1.1, Up: (dir) |
||
28 | |||
29 | FFTW FREQUENTLY ASKED QUESTIONS WITH ANSWERS |
||
30 | `date '+%d %h %Y'` |
||
31 | Matteo Frigo |
||
32 | Steven G. Johnson |
||
33 | <fftw@theory.lcs.mit.edu> |
||
34 | |||
35 | \endcopy |
||
36 | |||
37 | This is the list of Frequently Asked Questions about FFTW, a |
||
38 | collection of fast C routines for computing the Discrete Fourier |
||
39 | Transform in one or more dimensions. |
||
40 | |||
41 | \section Index |
||
42 | |||
43 | \index |
||
44 | |||
45 | \comment ###################################################################### |
||
46 | |||
47 | \section Introduction and General Information |
||
48 | |||
49 | \question 26aug:whatisfftw What is FFTW? |
||
50 | |||
51 | FFTW is a free collection of fast C routines for computing the |
||
52 | Discrete Fourier Transform in one or more dimensions. It includes |
||
53 | complex, real, and parallel transforms, and can handle arbitrary array |
||
54 | sizes efficiently. FFTW is typically faster than other |
||
55 | publically-available FFT implementations, and is even competitive with |
||
56 | vendor-tuned libraries. (See our web page for extensive benchmarks.) |
||
57 | To achieve this performance, FFTW uses novel code-generation and |
||
58 | runtime self-optimization techniques (along with many other tricks). |
||
59 | |||
60 | \question 26aug:whereisfftw How do I obtain FFTW? |
||
61 | |||
62 | FFTW can be found at \docref{the FFTW web page\}. You can also |
||
63 | retrieve it from \ftpon theory.lcs.mit.edu in \ftpin /pub/fftw. |
||
64 | |||
65 | \question 26aug:isfftwfree Is FFTW free software? |
||
66 | |||
67 | Starting with version 1.3, FFTW is Free Software in the technical |
||
68 | sense defined by the Free Software Foundation (see \docref{Categories |
||
69 | of Free and Non-Free Software\}), and is distributed under the terms |
||
70 | of the GNU General Public License. Previous versions of FFTW were |
||
71 | distributed without fee for noncommercial use, but were not |
||
72 | technically ``free.'' |
||
73 | |||
74 | Non-free licenses for FFTW are also available that permit different |
||
75 | terms of use than the GPL. |
||
76 | |||
77 | \question 10apr:nonfree What is this about non-free licenses? |
||
78 | |||
79 | The non-free licenses are for companies that wish to use FFTW in their |
||
80 | products but are unwilling to release their software under the GPL |
||
81 | (which would require them to release source code and allow free |
||
82 | redistribution). Such users can purchase an unlimited-use license |
||
83 | from MIT. Contact us for more details. |
||
84 | |||
85 | We could instead have released FFTW under the LGPL, or even disallowed |
||
86 | non-Free usage. Suffice it to say, however, that MIT owns the |
||
87 | copyright to FFTW and they only let us GPL it because we convinced |
||
88 | them that it would neither affect their licensing revenue nor irritate |
||
89 | existing licensees. |
||
90 | |||
91 | \comment ###################################################################### |
||
92 | |||
93 | \section Installing FFTW |
||
94 | |||
95 | \question 26aug:systems Which systems does FFTW run on? |
||
96 | |||
97 | FFTW is written in ANSI C, and should work on any system with |
||
98 | a decent C compiler. (See also \qref runOnDOS and |
||
99 | \qref compilerCrashes.) |
||
100 | |||
101 | \question 26aug:runOnDOS Does FFTW run on DOS/Windows? |
||
102 | |||
103 | It should. FFTW was not developed on DOS or Windows, but the source |
||
104 | code is straight ANSI C. Some users have reported using FFTW on |
||
105 | DOS/Windows using various compilers. See also the \docref{FFTW Windows |
||
106 | installation notes\} and \qref compilerCrashes |
||
107 | |||
108 | \question 26aug:compilerCrashes My compiler crashes when compiling FFTW. |
||
109 | |||
110 | Complain fiercely to the vendor of the compiler. |
||
111 | |||
112 | FFTW is a heavily-optimized piece of software that is likely to push |
||
113 | compilers to their limits. We had no problems with, for example, |
||
114 | \courier{gcc 2.7.2\}, Sun's \courier{SC4.0\}, IBM's \courier{XLC\}, |
||
115 | Metrowerks' compilers for the Macintosh, and SGI's compilers for IRIX |
||
116 | 6.2. Users have also reported successful compilations of FFTW using |
||
117 | Borland's C/C++ compilers on Windows. |
||
118 | |||
119 | Visual C++ 4.0 crashes when compiling FFTW 1.2 with all optimizations |
||
120 | turned on. Visual C++ 5.0 reportedly produces incorrect code for the |
||
121 | real transforms in FFTW 2.x when the option "Maximize speed" is set. |
||
122 | We are told that Service Pack 3 fixes the bug. |
||
123 | |||
124 | Various problems have also been observed with SGI's MIPSpro compilers, |
||
125 | versions 7.2.0 and 7.2.1 (you may have to lower the optimization level |
||
126 | for some files to get them to compile). The test program in earlier |
||
127 | versions of FFTW had problems with the \courier{-xO5\} option in Sun's |
||
128 | \courier{SC4.0\} C compiler. |
||
129 | |||
130 | \question 26aug:solarisSucks FFTW does not compile on Solaris, complaining about \courier{const\}. |
||
131 | |||
132 | We know that at least on Solaris 2.5.x with Sun's compilers 4.2 you |
||
133 | might get error messages from \courier{make\} such as |
||
134 | |||
135 | \courier{"./fftw.h", line 88: warning: const is a keyword in ANSI C\} |
||
136 | |||
137 | This is the case when the \courier{configure\} script reports that |
||
138 | \courier{const\} does not work: |
||
139 | |||
140 | \courier{checking for working const... (cached) no\} |
||
141 | |||
142 | You should be aware that Solaris comes with two compilers, namely, |
||
143 | \courier{/opt/SUNWspro/SC4.2/bin/cc\} and \courier{/usr/ucb/cc\}. The |
||
144 | latter compiler is non-ANSI. Indeed, it is a perverse shell script |
||
145 | that calls the real compiler in non-ANSI mode. In order |
||
146 | to compile FFTW, change your path so that the right \courier{cc\} |
||
147 | is used. |
||
148 | |||
149 | To know whether your compiler is the right one, type |
||
150 | \courier{cc -V\}. If the compiler prints ``\courier{ucbcc\}'', |
||
151 | as in |
||
152 | |||
153 | \courier{ucbcc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2\} |
||
154 | |||
155 | then the compiler is wrong. The right message is something like |
||
156 | |||
157 | \courier{cc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2\} |
||
158 | |||
159 | |||
160 | \question 26aug:languages Which language is FFTW written in? |
||
161 | |||
162 | FFTW is written in ANSI C. Most of the code, however, was |
||
163 | automatically generated by a program called \courier{genfft\}, written |
||
164 | in the Objective Caml dialect of ML. You do not need to know ML or to |
||
165 | have an Objective Caml compiler in order to use FFTW. |
||
166 | |||
167 | \courier{genfft\} is provided with the FFTW sources, which means that |
||
168 | you can play with the code generator if you want. In this case, you |
||
169 | need a working Objective Caml system. Objective Caml is available |
||
170 | from \ftpon ftp.inria.fr in the directory \ftpin /lang/caml-light. |
||
171 | |||
172 | \question 26aug:fortran Can I call FFTW from FORTRAN? |
||
173 | |||
174 | Yes, but not directly. The main problem is that Fortran cannot pass |
||
175 | parameters by value. However, FFTW can be called indirectly from |
||
176 | Fortran through the use of special C "wrapper" routines. Appropriate |
||
177 | wrapper code, documented in the FFTW manual, is included with FFTW |
||
178 | (versions 1.3 and higher). |
||
179 | |||
180 | \question 26aug:cplusplus Can I call FFTW from C++? |
||
181 | |||
182 | Most definitely. FFTW should compile and run under any C++ compiler. |
||
183 | |||
184 | \question 26aug:whynotfortran Why isn't FFTW written in FORTRAN/C++? |
||
185 | |||
186 | Because we don't like those languages, and neither approaches the |
||
187 | portability of C. |
||
188 | |||
189 | \question 29mar:singleprec How do I compile FFTW to run in single precision? |
||
190 | |||
191 | On a Unix system: \courier{configure --enable-float\}. On a non-Unix |
||
192 | system: edit \courier{fftw/fftw.h\} to \courier{#define\} the symbol |
||
193 | \courier{FFTW_ENABLE_FLOAT\}. In both cases, you must then recompile |
||
194 | FFTW. |
||
195 | |||
196 | \comment ###################################################################### |
||
197 | |||
198 | \section Using FFTW |
||
199 | |||
200 | \question 25may:slow FFTW seems really slow. |
||
201 | |||
202 | You are probably recreating the plan before every transform, rather |
||
203 | than creating it once and reusing it for all transforms of the same |
||
204 | size. FFTW is designed to be used in the following way: |
||
205 | |||
206 | \call startlist |
||
207 | \call item |
||
208 | First, you create a plan. This will take several seconds. |
||
209 | \call item |
||
210 | Then, you reuse the plan many times to perform FFTs. These are fast. |
||
211 | \call endlist |
||
212 | |||
213 | If you don't need to compute many transforms and the time for the |
||
214 | planner is significant, you have two options. First, you can use the |
||
215 | \courier{FFTW_ESTIMATE\} option in the planner, which uses heuristics |
||
216 | instead of runtime measurements and produces a good plan in a short |
||
217 | time. Second, you can use the wisdom feature to precompute the plan; |
||
218 | see \qref savePlans |
||
219 | |||
220 | \question 24mar:conventions FFTW gives results different from my old FFT. |
||
221 | |||
222 | People follow many different conventions for the DFT, and you should |
||
223 | be sure to know the ones that we use (described in the FFTW manual). |
||
224 | In particular, you should be aware that the |
||
225 | \courier{FFTW_FORWARD\}/\courier{FFTW_BACKWARD\} directions correspond |
||
226 | to signs of -1/+1 in the exponent of the DFT definition. |
||
227 | (\italic{Numerical Recipes\} uses the opposite convention.) |
||
228 | |||
229 | You should also know that we compute an unnormalized transform. In |
||
230 | contrast, Matlab is an example of program that computes a normalized |
||
231 | transform. See \qref whyscaled. |
||
232 | |||
233 | \question 26aug:savePlans Can I save FFTW's plans? |
||
234 | |||
235 | Yes. Starting with version 1.2, FFTW provides the |
||
236 | \courier{wisdom\} mechanism for saving plans. See \qref wisdom |
||
237 | and the FFTW manual. |
||
238 | |||
239 | \question 14sep:whyscaled Why does your inverse transform return a scaled result? |
||
240 | |||
241 | Computing the forward transform followed by the backward transform (or |
||
242 | vice versa) yields the original array scaled by the size of the array. |
||
243 | (For multi-dimensional transforms, the size of the array is the |
||
244 | product of the dimensions.) We could, instead, have chosen a |
||
245 | normalization that would have returned the unscaled array. Or, to |
||
246 | accomodate the many conventions in this matter, the transform routines |
||
247 | could have accepted a "scale factor" parameter. We did not do this, |
||
248 | however, for two reasons. First, we didn't want to sacrifice |
||
249 | performance in the common case where the scale factor is 1. Second, in |
||
250 | real applications the FFT is followed or preceded by some computation |
||
251 | on the data, into which the scale factor can typically be absorbed at |
||
252 | little or no cost. |
||
253 | |||
254 | \question 02dec:centerorigin How can I make FFTW put the origin (zero frequency) at the center of its output? |
||
255 | |||
256 | For human viewing of a spectrum, it is often convenient to put the |
||
257 | origin in frequency space at the center of the output array, rather |
||
258 | than in the zero-th element (the default in FFTW). If all of the |
||
259 | dimensions of your array are even, you can accomplish this by simply |
||
260 | multiplying each element of the input array by (-1)^(i + j + ...), |
||
261 | where i, j, etcetera are the indices of the element. (This trick is a |
||
262 | general property of the DFT, and is not specific to FFTW.) |
||
263 | |||
264 | \question 08may:imageaudio How do I FFT an image/audio file in \italic{foobar\} format? |
||
265 | |||
266 | FFTW performs an FFT on an array of floating-point values. You can |
||
267 | certainly use it to compute the transform of an image or audio stream, |
||
268 | but you are responsible for figuring out your data format and |
||
269 | converting it to the form FFTW requires. |
||
270 | |||
271 | \question 09apr:linkfails My program does not link (on Unix). |
||
272 | |||
273 | Please use the exact order in which libraries are specified by the |
||
274 | FFTW manual (e.g. \courier{-lrfftw -lfftw -lm\}). Also, note that the |
||
275 | libraries must be listed after your program sources/objects. (The |
||
276 | general rule is that if \italic{A\} uses \italic{B\}, then \italic{A\} |
||
277 | must be listed before \italic{B\} in the link command.). For example, |
||
278 | switching the order to \courier{-lfftw -lrfftw -lm\} will fail. |
||
279 | |||
280 | \comment ###################################################################### |
||
281 | |||
282 | \section Internals of FFTW |
||
283 | |||
284 | \question 26aug:howworks How does FFTW work? |
||
285 | |||
286 | The innovation (if it can be so called) in FFTW consists in having an |
||
287 | interpreter execute the transform. The program for the interpreter |
||
288 | (the \italic{plan\}) is computed at runtime according to the |
||
289 | characteristics of your machine/compiler. This peculiar software |
||
290 | architecture allows FFTW to adapt itself to almost any machine. |
||
291 | |||
292 | For more details, see the paper "The Fastest Fourier Transform in the |
||
293 | West", by M. Frigo and S. G. Johnson, available at \docref{the FFTW |
||
294 | web page\}. See also "FFTW: An Adaptive Software Architecture for the |
||
295 | FFT", in ICASSP '98. |
||
296 | |||
297 | \question 26aug:whyfast Why is FFTW so fast? |
||
298 | |||
299 | This is a complex question, and there is no simple answer. In fact, |
||
300 | the authors do not fully know the answer, either. In addition to many |
||
301 | small performance hacks throughout FFTW, there are three general |
||
302 | reasons for FFTW's speed. |
||
303 | |||
304 | \call startlist |
||
305 | \call item |
||
306 | FFTW uses an internal interpreter to adapt itself to |
||
307 | a machine. See \qref howworks. |
||
308 | \call item |
||
309 | FFTW uses a code generator to produce highly-optimized |
||
310 | routines for computing small transforms. |
||
311 | \call item |
||
312 | FFTW uses explicit divide-and-conquer to take advantage |
||
313 | of the memory hierarchy. |
||
314 | \call endlist |
||
315 | |||
316 | For more details on these three topics, see the paper "The Fastest |
||
317 | Fourier Transform in the West", by M. Frigo and S. G. Johnson, |
||
318 | available at \docref{the FFTW web page\}. |
||
319 | |||
320 | \question 26aug:wisdom What is this \courier{wisdom\} thing? |
||
321 | |||
322 | \courier{wisdom\} is the name of the mechanism that FFTW uses to save |
||
323 | and restore plans. Rather than just saving plans, FFTW remembers what |
||
324 | it learns about your machine, and becomes wiser and wiser as time |
||
325 | passes by. You can save \courier{wisdom\} for later use. |
||
326 | |||
327 | \question 26aug:whywisdom Why do you use \courier{wisdom\}? I just wanted to save a plan. |
||
328 | |||
329 | \courier{wisdom\} could be implemented with less effort than a general |
||
330 | plan-saving mechanism would have required. In addition, |
||
331 | \courier{wisdom\} provides additional benefits. For example, if you |
||
332 | are planning transforms of size 1024, and later you want a transform |
||
333 | of size 2048, most of the calculations of the 1024 case can be reused. |
||
334 | |||
335 | In short, \courier{wisdom\} does more things with less effort, and |
||
336 | seemed like The Right Thing to do. |
||
337 | |||
338 | \comment ###################################################################### |
||
339 | |||
340 | \section Known bugs |
||
341 | |||
342 | \question 27aug:rfftwndbug FFTW 1.1 crashes in rfftwnd on Linux. |
||
343 | |||
344 | This bug was fixed in FFTW 1.2. There was a bug in \courier{rfftwnd\} |
||
345 | causing an incorrect amount of memory to be allocated. The bug showed |
||
346 | up in Linux with libc-5.3.12 (and nowhere else that we know of). |
||
347 | |||
348 | \question 15oct:fftwmpibug The MPI transforms in FFTW 1.2 give incorrect results/leak memory. |
||
349 | |||
350 | These bugs were corrected in FFTW 1.2.1. The MPI transforms (really, |
||
351 | just the transpose routines) in FFTW 1.2 had bugs that could cause |
||
352 | errors in some situations. |
||
353 | |||
354 | \question 05nov:testsingbug The test programs in FFTW 1.2.1 fail when I change FFTW to use single precision. |
||
355 | |||
356 | This bug was fixed in FFTW 1.3. (Older versions of FFTW did |
||
357 | work in single precision, but the test programs didn't--the error |
||
358 | tolerances in the tests were set for double precision.) |
||
359 | |||
360 | \question 24mar:teststoobig The test program in FFTW 1.2.1 fails for n > 46340. |
||
361 | |||
362 | This bug was fixed in FFTW 1.3. FFTW 1.2.1 produced the right answer, |
||
363 | but the test program was wrong. For large n, n*n in the naive |
||
364 | transform that we used for comparison overflows 32 bit integer |
||
365 | precision, breaking the test. |
||
366 | |||
367 | \question 24aug:linuxthreads The threaded code fails on Linux Redhat 5.0 |
||
368 | |||
369 | We had problems with glibc-2.0.5. The code should work with |
||
370 | glibc-2.0.7. |
||
371 | |||
372 | \question 26sep:bigrfftwnd FFTW 2.0's rfftwnd fails for rank > 1 transforms with a final dimension >= 65536. |
||
373 | |||
374 | This bug was fixed in FFTW 2.0.1. (There was a 32-bit integer overflow due |
||
375 | to a poorly-parenthesized expression.) |
||
376 | |||
377 | \question 26mar:primebug FFTW 2.0's complex transforms give the wrong results with prime factors 17 to 97. |
||
378 | |||
379 | There was a bug in the complex transforms that could cause incorrect |
||
380 | results under (hopefully rare) circumstances for lengths with |
||
381 | intermediate-size prime factors (17-97). This bug was fixed in FFTW |
||
382 | 2.1.1. |
||
383 | |||
384 | \question 05apr:mpichbug FFTW 2.1.1's MPI test programs crash with MPICH. |
||
385 | |||
386 | This was fixed in FFTW 2.1.2. The 2.1/2.1.1 MPI test programs crashed |
||
387 | when using the MPICH implementation of MPI with the \courier{ch_p4\} |
||
388 | device (TCP/IP); the transforms themselves worked fine. (The source |
||
389 | of the bug was some strange constraints that MPICH imposes on access |
||
390 | to the program argument list.) |
||
391 | |||
392 | \comment Here it ends! |