Rev 2 | Blame | Compare with Previous | Last modification | View Log | RSS feed

`FFTW FREQUENTLY ASKED QUESTIONS WITH ANSWERS`

`18 May 1999`

`Matteo Frigo`

`Steven G. Johnson`

`<fftw@theory.lcs.mit.edu>`

`This is the list of Frequently Asked Questions about FFTW, a collection of`

`fast C routines for computing the Discrete Fourier Transform in one or`

`more dimensions.`

`===============================================================================`

`Index`

`Section 1. Introduction and General Information`

`Q1.1 What is FFTW?`

`Q1.2 How do I obtain FFTW?`

`Q1.3 Is FFTW free software?`

`Q1.4 What is this about non-free licenses?`

`Section 2. Installing FFTW`

`Q2.1 Which systems does FFTW run on?`

`Q2.2 Does FFTW run on DOS/Windows?`

`Q2.3 My compiler crashes when compiling FFTW.`

`Q2.4 FFTW does not compile on Solaris, complaining about const.`

`Q2.5 Which language is FFTW written in?`

`Q2.6 Can I call FFTW from FORTRAN?`

`Q2.7 Can I call FFTW from C++?`

`Q2.8 Why isn't FFTW written in FORTRAN/C++?`

`Q2.9 How do I compile FFTW to run in single precision?`

`Section 3. Using FFTW`

`Q3.1 FFTW seems really slow.`

`Q3.2 FFTW gives results different from my old FFT.`

`Q3.3 Can I save FFTW's plans?`

`Q3.4 Why does your inverse transform return a scaled result?`

`Q3.5 How can I make FFTW put the origin (zero frequency) at the center`

`Q3.6 How do I FFT an image/audio file in *foobar* format?`

`Q3.7 My program does not link (on Unix).`

`Section 4. Internals of FFTW`

`Q4.1 How does FFTW work?`

`Q4.2 Why is FFTW so fast?`

`Q4.3 What is this wisdom thing?`

`Q4.4 Why do you use wisdom? I just wanted to save a plan.`

`Section 5. Known bugs`

`Q5.1 FFTW 1.1 crashes in rfftwnd on Linux.`

`Q5.2 The MPI transforms in FFTW 1.2 give incorrect results/leak memory.`

`Q5.3 The test programs in FFTW 1.2.1 fail when I change FFTW to use sin`

`Q5.4 The test program in FFTW 1.2.1 fails for n > 46340.`

`Q5.5 The threaded code fails on Linux Redhat 5.0`

`Q5.6 FFTW 2.0's rfftwnd fails for rank > 1 transforms with a final dime`

`Q5.7 FFTW 2.0's complex transforms give the wrong results with prime fa`

`Q5.8 FFTW 2.1.1's MPI test programs crash with MPICH.`

`===============================================================================`

`Section 1. Introduction and General Information`

`Q1.1 What is FFTW?`

`Q1.2 How do I obtain FFTW?`

`Q1.3 Is FFTW free software?`

`Q1.4 What is this about non-free licenses?`

`-------------------------------------------------------------------------------`

`Question 1.1. What is FFTW?`

`FFTW is a free collection of fast C routines for computing the Discrete`

`Fourier Transform in one or more dimensions. It includes complex, real,`

`and parallel transforms, and can handle arbitrary array sizes efficiently.`

`FFTW is typically faster than other publically-available FFT`

`implementations, and is even competitive with vendor-tuned libraries.`

`(See our web page for extensive benchmarks.) To achieve this performance,`

`FFTW uses novel code-generation and runtime self-optimization techniques`

`(along with many other tricks).`

`-------------------------------------------------------------------------------`

`Question 1.2. How do I obtain FFTW?`

`FFTW can be found at the FFTW web page. You can also retrieve it from`

`theory.lcs.mit.edu in /pub/fftw.`

`-------------------------------------------------------------------------------`

`Question 1.3. Is FFTW free software?`

`Starting with version 1.3, FFTW is Free Software in the technical sense`

`defined by the Free Software Foundation (see Categories of Free and`

`Non-Free Software), and is distributed under the terms of the GNU General`

`Public License. Previous versions of FFTW were distributed without fee`

`for noncommercial use, but were not technically ``free.''`

`Non-free licenses for FFTW are also available that permit different terms`

`of use than the GPL.`

`-------------------------------------------------------------------------------`

`Question 1.4. What is this about non-free licenses?`

`The non-free licenses are for companies that wish to use FFTW in their`

`products but are unwilling to release their software under the GPL (which`

`would require them to release source code and allow free redistribution).`

`Such users can purchase an unlimited-use license from MIT. Contact us for`

`more details.`

`We could instead have released FFTW under the LGPL, or even disallowed`

`non-Free usage. Suffice it to say, however, that MIT owns the copyright`

`to FFTW and they only let us GPL it because we convinced them that it`

`would neither affect their licensing revenue nor irritate existing`

`licensees.`

`===============================================================================`

`Section 2. Installing FFTW`

`Q2.1 Which systems does FFTW run on?`

`Q2.2 Does FFTW run on DOS/Windows?`

`Q2.3 My compiler crashes when compiling FFTW.`

`Q2.4 FFTW does not compile on Solaris, complaining about const.`

`Q2.5 Which language is FFTW written in?`

`Q2.6 Can I call FFTW from FORTRAN?`

`Q2.7 Can I call FFTW from C++?`

`Q2.8 Why isn't FFTW written in FORTRAN/C++?`

`Q2.9 How do I compile FFTW to run in single precision?`

`-------------------------------------------------------------------------------`

`Question 2.1. Which systems does FFTW run on?`

`FFTW is written in ANSI C, and should work on any system with a decent C`

`compiler. (See also Q2.2 `Does FFTW run on DOS/Windows?' and Q2.3 `My`

`compiler crashes when compiling FFTW.'.)`

`-------------------------------------------------------------------------------`

`Question 2.2. Does FFTW run on DOS/Windows?`

`It should. FFTW was not developed on DOS or Windows, but the source code`

`is straight ANSI C. Some users have reported using FFTW on DOS/Windows`

`using various compilers. See also the FFTW Windows installation notes and`

`Q2.3 `My compiler crashes when compiling FFTW.'`

`-------------------------------------------------------------------------------`

`Question 2.3. My compiler crashes when compiling FFTW.`

`Complain fiercely to the vendor of the compiler.`

`FFTW is a heavily-optimized piece of software that is likely to push`

`compilers to their limits. We had no problems with, for example, gcc`

`2.7.2, Sun's SC4.0, IBM's XLC, Metrowerks' compilers for the Macintosh,`

`and SGI's compilers for IRIX 6.2. Users have also reported successful`

`compilations of FFTW using Borland's C/C++ compilers on Windows.`

`Visual C++ 4.0 crashes when compiling FFTW 1.2 with all optimizations`

`turned on. Visual C++ 5.0 reportedly produces incorrect code for the real`

`transforms in FFTW 2.x when the option "Maximize speed" is set. We are`

`told that Service Pack 3 fixes the bug.`

`Various problems have also been observed with SGI's MIPSpro compilers,`

`versions 7.2.0 and 7.2.1 (you may have to lower the optimization level for`

`some files to get them to compile). The test program in earlier versions`

`of FFTW had problems with the -xO5 option in Sun's SC4.0 C compiler.`

`-------------------------------------------------------------------------------`

`Question 2.4. FFTW does not compile on Solaris, complaining about const.`

`We know that at least on Solaris 2.5.x with Sun's compilers 4.2 you might`

`get error messages from make such as`

`"./fftw.h", line 88: warning: const is a keyword in ANSI C`

`This is the case when the configure script reports that const does not`

`work:`

`checking for working const... (cached) no`

`You should be aware that Solaris comes with two compilers, namely,`

`/opt/SUNWspro/SC4.2/bin/cc and /usr/ucb/cc. The latter compiler is`

`non-ANSI. Indeed, it is a perverse shell script that calls the real`

`compiler in non-ANSI mode. In order to compile FFTW, change your path so`

`that the right cc is used.`

`To know whether your compiler is the right one, type cc -V. If the`

`compiler prints ``ucbcc'', as in`

`ucbcc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2`

`then the compiler is wrong. The right message is something like`

`cc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2`

`-------------------------------------------------------------------------------`

`Question 2.5. Which language is FFTW written in?`

`FFTW is written in ANSI C. Most of the code, however, was automatically`

`generated by a program called genfft, written in the Objective Caml`

`dialect of ML. You do not need to know ML or to have an Objective Caml`

`compiler in order to use FFTW.`

`genfft is provided with the FFTW sources, which means that you can play`

`with the code generator if you want. In this case, you need a working`

`Objective Caml system. Objective Caml is available from ftp.inria.fr in`

`the directory /lang/caml-light.`

`-------------------------------------------------------------------------------`

`Question 2.6. Can I call FFTW from FORTRAN?`

`Yes, but not directly. The main problem is that Fortran cannot pass`

`parameters by value. However, FFTW can be called indirectly from Fortran`

`through the use of special C "wrapper" routines. Appropriate wrapper`

`code, documented in the FFTW manual, is included with FFTW (versions 1.3`

`and higher).`

`-------------------------------------------------------------------------------`

`Question 2.7. Can I call FFTW from C++?`

`Most definitely. FFTW should compile and run under any C++ compiler.`

`-------------------------------------------------------------------------------`

`Question 2.8. Why isn't FFTW written in FORTRAN/C++?`

`Because we don't like those languages, and neither approaches the`

`portability of C.`

`-------------------------------------------------------------------------------`

`Question 2.9. How do I compile FFTW to run in single precision?`

`On a Unix system: configure --enable-float. On a non-Unix system: edit`

`fftw/fftw.h to #define the symbol FFTW_ENABLE_FLOAT. In both cases, you`

`must then recompile FFTW.`

`===============================================================================`

`Section 3. Using FFTW`

`Q3.1 FFTW seems really slow.`

`Q3.2 FFTW gives results different from my old FFT.`

`Q3.3 Can I save FFTW's plans?`

`Q3.4 Why does your inverse transform return a scaled result?`

`Q3.5 How can I make FFTW put the origin (zero frequency) at the center`

`Q3.6 How do I FFT an image/audio file in *foobar* format?`

`Q3.7 My program does not link (on Unix).`

`-------------------------------------------------------------------------------`

`Question 3.1. FFTW seems really slow.`

`You are probably recreating the plan before every transform, rather than`

`creating it once and reusing it for all transforms of the same size. FFTW`

`is designed to be used in the following way:`

`* First, you create a plan. This will take several seconds.`

`* Then, you reuse the plan many times to perform FFTs. These are fast.`

`If you don't need to compute many transforms and the time for the planner`

`is significant, you have two options. First, you can use the`

`FFTW_ESTIMATE option in the planner, which uses heuristics instead of`

`runtime measurements and produces a good plan in a short time. Second,`

`you can use the wisdom feature to precompute the plan; see Q3.3 `Can I`

`save FFTW's plans?'`

`-------------------------------------------------------------------------------`

`Question 3.2. FFTW gives results different from my old FFT.`

`People follow many different conventions for the DFT, and you should be`

`sure to know the ones that we use (described in the FFTW manual). In`

`particular, you should be aware that the FFTW_FORWARD/FFTW_BACKWARD`

`directions correspond to signs of -1/+1 in the exponent of the DFT`

`definition. (*Numerical Recipes* uses the opposite convention.)`

`You should also know that we compute an unnormalized transform. In`

`contrast, Matlab is an example of program that computes a normalized`

`transform. See Q3.4 `Why does your inverse transform return a scaled`

`result?'.`

`-------------------------------------------------------------------------------`

`Question 3.3. Can I save FFTW's plans?`

`Yes. Starting with version 1.2, FFTW provides the wisdom mechanism for`

`saving plans. See Q4.3 `What is this wisdom thing?' and the FFTW manual.`

`-------------------------------------------------------------------------------`

`Question 3.4. Why does your inverse transform return a scaled result?`

`Computing the forward transform followed by the backward transform (or`

`vice versa) yields the original array scaled by the size of the array.`

`(For multi-dimensional transforms, the size of the array is the product of`

`the dimensions.) We could, instead, have chosen a normalization that`

`would have returned the unscaled array. Or, to accomodate the many`

`conventions in this matter, the transform routines could have accepted a`

`"scale factor" parameter. We did not do this, however, for two reasons.`

`First, we didn't want to sacrifice performance in the common case where`

`the scale factor is 1. Second, in real applications the FFT is followed or`

`preceded by some computation on the data, into which the scale factor can`

`typically be absorbed at little or no cost.`

`-------------------------------------------------------------------------------`

`Question 3.5. How can I make FFTW put the origin (zero frequency) at the center of its output?`

`For human viewing of a spectrum, it is often convenient to put the origin`

`in frequency space at the center of the output array, rather than in the`

`zero-th element (the default in FFTW). If all of the dimensions of your`

`array are even, you can accomplish this by simply multiplying each element`

`of the input array by (-1)^(i + j + ...), where i, j, etcetera are the`

`indices of the element. (This trick is a general property of the DFT, and`

`is not specific to FFTW.)`

`-------------------------------------------------------------------------------`

`Question 3.6. How do I FFT an image/audio file in *foobar* format?`

`FFTW performs an FFT on an array of floating-point values. You can`

`certainly use it to compute the transform of an image or audio stream, but`

`you are responsible for figuring out your data format and converting it to`

`the form FFTW requires.`

`-------------------------------------------------------------------------------`

`Question 3.7. My program does not link (on Unix).`

`Please use the exact order in which libraries are specified by the FFTW`

`manual (e.g. -lrfftw -lfftw -lm). Also, note that the libraries must be`

`listed after your program sources/objects. (The general rule is that if`

`*A* uses *B*, then *A* must be listed before *B* in the link command.).`

`For example, switching the order to -lfftw -lrfftw -lm will fail.`

`===============================================================================`

`Section 4. Internals of FFTW`

`Q4.1 How does FFTW work?`

`Q4.2 Why is FFTW so fast?`

`Q4.3 What is this wisdom thing?`

`Q4.4 Why do you use wisdom? I just wanted to save a plan.`

`-------------------------------------------------------------------------------`

`Question 4.1. How does FFTW work?`

`The innovation (if it can be so called) in FFTW consists in having an`

`interpreter execute the transform. The program for the interpreter (the`

`*plan*) is computed at runtime according to the characteristics of your`

`machine/compiler. This peculiar software architecture allows FFTW to`

`adapt itself to almost any machine.`

`For more details, see the paper "The Fastest Fourier Transform in the`

`West", by M. Frigo and S. G. Johnson, available at the FFTW web page. See`

`also "FFTW: An Adaptive Software Architecture for the FFT", in ICASSP '98.`

`-------------------------------------------------------------------------------`

`Question 4.2. Why is FFTW so fast?`

`This is a complex question, and there is no simple answer. In fact, the`

`authors do not fully know the answer, either. In addition to many small`

`performance hacks throughout FFTW, there are three general reasons for`

`FFTW's speed.`

`* FFTW uses an internal interpreter to adapt itself to a machine. See`

`Q4.1 `How does FFTW work?'.`

`* FFTW uses a code generator to produce highly-optimized routines for`

`computing small transforms.`

`* FFTW uses explicit divide-and-conquer to take advantage of the memory`

`hierarchy.`

`For more details on these three topics, see the paper "The Fastest Fourier`

`Transform in the West", by M. Frigo and S. G. Johnson, available at the`

`FFTW web page.`

`-------------------------------------------------------------------------------`

`Question 4.3. What is this wisdom thing?`

`wisdom is the name of the mechanism that FFTW uses to save and restore`

`plans. Rather than just saving plans, FFTW remembers what it learns about`

`your machine, and becomes wiser and wiser as time passes by. You can save`

`wisdom for later use.`

`-------------------------------------------------------------------------------`

`Question 4.4. Why do you use wisdom? I just wanted to save a plan.`

`wisdom could be implemented with less effort than a general plan-saving`

`mechanism would have required. In addition, wisdom provides additional`

`benefits. For example, if you are planning transforms of size 1024, and`

`later you want a transform of size 2048, most of the calculations of the`

`1024 case can be reused.`

`In short, wisdom does more things with less effort, and seemed like The`

`Right Thing to do.`

`===============================================================================`

`Section 5. Known bugs`

`Q5.1 FFTW 1.1 crashes in rfftwnd on Linux.`

`Q5.2 The MPI transforms in FFTW 1.2 give incorrect results/leak memory.`

`Q5.3 The test programs in FFTW 1.2.1 fail when I change FFTW to use sin`

`Q5.4 The test program in FFTW 1.2.1 fails for n > 46340.`

`Q5.5 The threaded code fails on Linux Redhat 5.0`

`Q5.6 FFTW 2.0's rfftwnd fails for rank > 1 transforms with a final dime`

`Q5.7 FFTW 2.0's complex transforms give the wrong results with prime fa`

`Q5.8 FFTW 2.1.1's MPI test programs crash with MPICH.`

`-------------------------------------------------------------------------------`

`Question 5.1. FFTW 1.1 crashes in rfftwnd on Linux.`

`This bug was fixed in FFTW 1.2. There was a bug in rfftwnd causing an`

`incorrect amount of memory to be allocated. The bug showed up in Linux`

`with libc-5.3.12 (and nowhere else that we know of).`

`-------------------------------------------------------------------------------`

`Question 5.2. The MPI transforms in FFTW 1.2 give incorrect results/leak memory.`

`These bugs were corrected in FFTW 1.2.1. The MPI transforms (really, just`

`the transpose routines) in FFTW 1.2 had bugs that could cause errors in`

`some situations.`

`-------------------------------------------------------------------------------`

`Question 5.3. The test programs in FFTW 1.2.1 fail when I change FFTW to use single precision.`

`This bug was fixed in FFTW 1.3. (Older versions of FFTW did work in`

`single precision, but the test programs didn't--the error tolerances in`

`the tests were set for double precision.)`

`-------------------------------------------------------------------------------`

`Question 5.4. The test program in FFTW 1.2.1 fails for n > 46340.`

`This bug was fixed in FFTW 1.3. FFTW 1.2.1 produced the right answer, but`

`the test program was wrong. For large n, n*n in the naive transform that`

`we used for comparison overflows 32 bit integer precision, breaking the`

`test.`

`-------------------------------------------------------------------------------`

`Question 5.5. The threaded code fails on Linux Redhat 5.0`

`We had problems with glibc-2.0.5. The code should work with glibc-2.0.7.`

`-------------------------------------------------------------------------------`

`Question 5.6. FFTW 2.0's rfftwnd fails for rank > 1 transforms with a final dimension >= 65536.`

`This bug was fixed in FFTW 2.0.1. (There was a 32-bit integer overflow`

`due to a poorly-parenthesized expression.)`

`-------------------------------------------------------------------------------`

`Question 5.7. FFTW 2.0's complex transforms give the wrong results with prime factors 17 to 97.`

`There was a bug in the complex transforms that could cause incorrect`

`results under (hopefully rare) circumstances for lengths with`

`intermediate-size prime factors (17-97). This bug was fixed in FFTW`

`2.1.1.`

`-------------------------------------------------------------------------------`

`Question 5.8. FFTW 2.1.1's MPI test programs crash with MPICH.`

`This was fixed in FFTW 2.1.2. The 2.1/2.1.1 MPI test programs crashed`

`when using the MPICH implementation of MPI with the ch_p4 device (TCP/IP);`

`the transforms themselves worked fine. (The source of the bug was some`

`strange constraints that MPICH imposes on access to the program argument`

`list.)`