Subversion Repositories shark

Rev

Rev 3 | Details | Compare with Previous | 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!