cannam@127: FFTW FREQUENTLY ASKED QUESTIONS WITH ANSWERS cannam@127: 30 Jul 2016 cannam@127: Matteo Frigo cannam@127: Steven G. Johnson cannam@127: cannam@127: cannam@127: This is the list of Frequently Asked Questions about FFTW, a collection of cannam@127: fast C routines for computing the Discrete Fourier Transform in one or cannam@127: more dimensions. cannam@127: cannam@127: =============================================================================== cannam@127: cannam@127: Index cannam@127: cannam@127: Section 1. Introduction and General Information cannam@127: Q1.1 What is FFTW? cannam@127: Q1.2 How do I obtain FFTW? cannam@127: Q1.3 Is FFTW free software? cannam@127: Q1.4 What is this about non-free licenses? cannam@127: Q1.5 In the West? I thought MIT was in the East? cannam@127: cannam@127: Section 2. Installing FFTW cannam@127: Q2.1 Which systems does FFTW run on? cannam@127: Q2.2 Does FFTW run on Windows? cannam@127: Q2.3 My compiler has trouble with FFTW. cannam@127: Q2.4 FFTW does not compile on Solaris, complaining about const. cannam@127: Q2.5 What's the difference between --enable-3dnow and --enable-k7? cannam@127: Q2.6 What's the difference between the fma and the non-fma versions? cannam@127: Q2.7 Which language is FFTW written in? cannam@127: Q2.8 Can I call FFTW from Fortran? cannam@127: Q2.9 Can I call FFTW from C++? cannam@127: Q2.10 Why isn't FFTW written in Fortran/C++? cannam@127: Q2.11 How do I compile FFTW to run in single precision? cannam@127: Q2.12 --enable-k7 does not work on x86-64 cannam@127: cannam@127: Section 3. Using FFTW cannam@127: Q3.1 Why not support the FFTW 2 interface in FFTW 3? cannam@127: Q3.2 Why do FFTW 3 plans encapsulate the input/output arrays and not ju cannam@127: Q3.3 FFTW seems really slow. cannam@127: Q3.4 FFTW slows down after repeated calls. cannam@127: Q3.5 An FFTW routine is crashing when I call it. cannam@127: Q3.6 My Fortran program crashes when calling FFTW. cannam@127: Q3.7 FFTW gives results different from my old FFT. cannam@127: Q3.8 FFTW gives different results between runs cannam@127: Q3.9 Can I save FFTW's plans? cannam@127: Q3.10 Why does your inverse transform return a scaled result? cannam@127: Q3.11 How can I make FFTW put the origin (zero frequency) at the center cannam@127: Q3.12 How do I FFT an image/audio file in *foobar* format? cannam@127: Q3.13 My program does not link (on Unix). cannam@127: Q3.14 I included your header, but linking still fails. cannam@127: Q3.15 My program crashes, complaining about stack space. cannam@127: Q3.16 FFTW seems to have a memory leak. cannam@127: Q3.17 The output of FFTW's transform is all zeros. cannam@127: Q3.18 How do I call FFTW from the Microsoft language du jour? cannam@127: Q3.19 Can I compute only a subset of the DFT outputs? cannam@127: Q3.20 Can I use FFTW's routines for in-place and out-of-place matrix tra cannam@127: cannam@127: Section 4. Internals of FFTW cannam@127: Q4.1 How does FFTW work? cannam@127: Q4.2 Why is FFTW so fast? cannam@127: cannam@127: Section 5. Known bugs cannam@127: Q5.1 FFTW 1.1 crashes in rfftwnd on Linux. cannam@127: Q5.2 The MPI transforms in FFTW 1.2 give incorrect results/leak memory. cannam@127: Q5.3 The test programs in FFTW 1.2.1 fail when I change FFTW to use sin cannam@127: Q5.4 The test program in FFTW 1.2.1 fails for n > 46340. cannam@127: Q5.5 The threaded code fails on Linux Redhat 5.0 cannam@127: Q5.6 FFTW 2.0's rfftwnd fails for rank > 1 transforms with a final dime cannam@127: Q5.7 FFTW 2.0's complex transforms give the wrong results with prime fa cannam@127: Q5.8 FFTW 2.1.1's MPI test programs crash with MPICH. cannam@127: Q5.9 FFTW 2.1.2's multi-threaded transforms don't work on AIX. cannam@127: Q5.10 FFTW 2.1.2's complex transforms give incorrect results for large p cannam@127: Q5.11 FFTW 2.1.3's multi-threaded transforms don't give any speedup on S cannam@127: Q5.12 FFTW 2.1.3 crashes on AIX. cannam@127: cannam@127: =============================================================================== cannam@127: cannam@127: Section 1. Introduction and General Information cannam@127: cannam@127: Q1.1 What is FFTW? cannam@127: Q1.2 How do I obtain FFTW? cannam@127: Q1.3 Is FFTW free software? cannam@127: Q1.4 What is this about non-free licenses? cannam@127: Q1.5 In the West? I thought MIT was in the East? cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 1.1. What is FFTW? cannam@127: cannam@127: FFTW is a free collection of fast C routines for computing the Discrete cannam@127: Fourier Transform in one or more dimensions. It includes complex, real, cannam@127: symmetric, and parallel transforms, and can handle arbitrary array sizes cannam@127: efficiently. FFTW is typically faster than other publically-available FFT cannam@127: implementations, and is even competitive with vendor-tuned libraries. cannam@127: (See our web page for extensive benchmarks.) To achieve this performance, cannam@127: FFTW uses novel code-generation and runtime self-optimization techniques cannam@127: (along with many other tricks). cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 1.2. How do I obtain FFTW? cannam@127: cannam@127: FFTW can be found at the FFTW web page. You can also retrieve it from cannam@127: ftp.fftw.org in /pub/fftw. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 1.3. Is FFTW free software? cannam@127: cannam@127: Starting with version 1.3, FFTW is Free Software in the technical sense cannam@127: defined by the Free Software Foundation (see Categories of Free and cannam@127: Non-Free Software), and is distributed under the terms of the GNU General cannam@127: Public License. Previous versions of FFTW were distributed without fee cannam@127: for noncommercial use, but were not technically ``free.'' cannam@127: cannam@127: Non-free licenses for FFTW are also available that permit different terms cannam@127: of use than the GPL. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 1.4. What is this about non-free licenses? cannam@127: cannam@127: The non-free licenses are for companies that wish to use FFTW in their cannam@127: products but are unwilling to release their software under the GPL (which cannam@127: would require them to release source code and allow free redistribution). cannam@127: Such users can purchase an unlimited-use license from MIT. Contact us for cannam@127: more details. cannam@127: cannam@127: We could instead have released FFTW under the LGPL, or even disallowed cannam@127: non-Free usage. Suffice it to say, however, that MIT owns the copyright cannam@127: to FFTW and they only let us GPL it because we convinced them that it cannam@127: would neither affect their licensing revenue nor irritate existing cannam@127: licensees. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 1.5. In the West? I thought MIT was in the East? cannam@127: cannam@127: Not to an Italian. You could say that we're a Spaghetti Western (with cannam@127: apologies to Sergio Leone). cannam@127: cannam@127: =============================================================================== cannam@127: cannam@127: Section 2. Installing FFTW cannam@127: cannam@127: Q2.1 Which systems does FFTW run on? cannam@127: Q2.2 Does FFTW run on Windows? cannam@127: Q2.3 My compiler has trouble with FFTW. cannam@127: Q2.4 FFTW does not compile on Solaris, complaining about const. cannam@127: Q2.5 What's the difference between --enable-3dnow and --enable-k7? cannam@127: Q2.6 What's the difference between the fma and the non-fma versions? cannam@127: Q2.7 Which language is FFTW written in? cannam@127: Q2.8 Can I call FFTW from Fortran? cannam@127: Q2.9 Can I call FFTW from C++? cannam@127: Q2.10 Why isn't FFTW written in Fortran/C++? cannam@127: Q2.11 How do I compile FFTW to run in single precision? cannam@127: Q2.12 --enable-k7 does not work on x86-64 cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.1. Which systems does FFTW run on? cannam@127: cannam@127: FFTW is written in ANSI C, and should work on any system with a decent C cannam@127: compiler. (See also Q2.2 `Does FFTW run on Windows?', Q2.3 `My compiler cannam@127: has trouble with FFTW.'.) FFTW can also take advantage of certain cannam@127: hardware-specific features, such as cycle counters and SIMD instructions, cannam@127: but this is optional. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.2. Does FFTW run on Windows? cannam@127: cannam@127: Yes, many people have reported successfully using FFTW on Windows with cannam@127: various compilers. FFTW was not developed on Windows, but the source code cannam@127: is essentially straight ANSI C. See also the FFTW Windows installation cannam@127: notes, Q2.3 `My compiler has trouble with FFTW.', and Q3.18 `How do I call cannam@127: FFTW from the Microsoft language du jour?'. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.3. My compiler has trouble with FFTW. cannam@127: cannam@127: Complain fiercely to the vendor of the compiler. cannam@127: cannam@127: We have successfully used gcc 3.2.x on x86 and PPC, a recent Compaq C cannam@127: compiler for Alpha, version 6 of IBM's xlc compiler for AIX, Intel's icc cannam@127: versions 5-7, and Sun WorkShop cc version 6. cannam@127: cannam@127: FFTW is likely to push compilers to their limits, however, and several cannam@127: compiler bugs have been exposed by FFTW. A partial list follows. cannam@127: cannam@127: gcc 2.95.x for Solaris/SPARC produces incorrect code for the test program cannam@127: (workaround: recompile the libbench2 directory with -O2). cannam@127: cannam@127: NetBSD/macppc 1.6 comes with a gcc version that also miscompiles the test cannam@127: program. (Please report a workaround if you know one.) cannam@127: cannam@127: gcc 3.2.3 for ARM reportedly crashes during compilation. This bug is cannam@127: reportedly fixed in later versions of gcc. cannam@127: cannam@127: Versions 8.0 and 8.1 of Intel's icc falsely claim to be gcc, so you should cannam@127: specify CC="icc -no-gcc"; this is automatic in FFTW 3.1. icc-8.0.066 cannam@127: reportely produces incorrect code for FFTW 2.1.5, but is fixed in version cannam@127: 8.1. icc-7.1 compiler build 20030402Z appears to produce incorrect cannam@127: dependencies, causing the compilation to fail. icc-7.1 build 20030307Z cannam@127: appears to work fine. (Use icc -V to check which build you have.) As of cannam@127: 2003/04/18, build 20030402Z appears not to be available any longer on cannam@127: Intel's website, whereas the older build 20030307Z is available. cannam@127: cannam@127: ranlib of GNU binutils 2.9.1 on Irix has been observed to corrupt the FFTW cannam@127: libraries, causing a link failure when FFTW is compiled. Since ranlib is cannam@127: completely superfluous on Irix, we suggest deleting it from your system cannam@127: and replacing it with a symbolic link to /bin/echo. cannam@127: cannam@127: If support for SIMD instructions is enabled in FFTW, further compiler cannam@127: problems may appear: cannam@127: cannam@127: gcc 3.4.[0123] for x86 produces incorrect SSE2 code for FFTW when -O2 (the cannam@127: best choice for FFTW) is used, causing FFTW to crash (make check crashes). cannam@127: This bug is fixed in gcc 3.4.4. On x86_64 (amd64/em64t), gcc 3.4.4 cannam@127: reportedly still has a similar problem, but this is fixed as of gcc 3.4.6. cannam@127: cannam@127: gcc-3.2 for x86 produces incorrect SIMD code if -O3 is used. The same cannam@127: compiler produces incorrect SIMD code if no optimization is used, too. cannam@127: When using gcc-3.2, it is a good idea not to change the default CFLAGS cannam@127: selected by the configure script. cannam@127: cannam@127: Some 3.0.x and 3.1.x versions of gcc on x86 may crash. gcc so-called 2.96 cannam@127: shipping with RedHat 7.3 crashes when compiling SIMD code. In both cases, cannam@127: please upgrade to gcc-3.2 or later. cannam@127: cannam@127: Intel's icc 6.0 misaligns SSE constants, but FFTW has a workaround. icc cannam@127: 8.x fails to compile FFTW 3.0.x because it falsely claims to be gcc; we cannam@127: believe this to be a bug in icc, but FFTW 3.1 has a workaround. cannam@127: cannam@127: Visual C++ 2003 reportedly produces incorrect code for SSE/SSE2 when cannam@127: compiling FFTW. This bug was reportedly fixed in VC++ 2005; cannam@127: alternatively, you could switch to the Intel compiler. VC++ 6.0 also cannam@127: reportedly produces incorrect code for the file reodft11e-r2hc-odd.c cannam@127: unless optimizations are disabled for that file. cannam@127: cannam@127: gcc 2.95 on MacOS X miscompiles AltiVec code (fixed in later versions). cannam@127: gcc 3.2.x miscompiles AltiVec permutations, but FFTW has a workaround. cannam@127: gcc 4.0.1 on MacOS for Intel crashes when compiling FFTW; a workaround is cannam@127: to compile one file without optimization: cd kernel; make CFLAGS=" " cannam@127: trig.lo. cannam@127: cannam@127: gcc 4.1.1 reportedly crashes when compiling FFTW for MIPS; the workaround cannam@127: is to compile the file it crashes on (t2_64.c) with a lower optimization cannam@127: level. cannam@127: cannam@127: gcc versions 4.1.2 to 4.2.0 for x86 reportedly miscompile FFTW 3.1's test cannam@127: program, causing make check to crash (gcc bug #26528). The bug was cannam@127: reportedly fixed in gcc version 4.2.1 and later. A workaround is to cannam@127: compile libbench2/verify-lib.c without optimization. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.4. FFTW does not compile on Solaris, complaining about const. cannam@127: cannam@127: We know that at least on Solaris 2.5.x with Sun's compilers 4.2 you might cannam@127: get error messages from make such as cannam@127: cannam@127: "./fftw.h", line 88: warning: const is a keyword in ANSI C cannam@127: cannam@127: This is the case when the configure script reports that const does not cannam@127: work: cannam@127: cannam@127: checking for working const... (cached) no cannam@127: cannam@127: You should be aware that Solaris comes with two compilers, namely, cannam@127: /opt/SUNWspro/SC4.2/bin/cc and /usr/ucb/cc. The latter compiler is cannam@127: non-ANSI. Indeed, it is a perverse shell script that calls the real cannam@127: compiler in non-ANSI mode. In order to compile FFTW, change your path so cannam@127: that the right cc is used. cannam@127: cannam@127: To know whether your compiler is the right one, type cc -V. If the cannam@127: compiler prints ``ucbcc'', as in cannam@127: cannam@127: ucbcc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2 cannam@127: cannam@127: then the compiler is wrong. The right message is something like cannam@127: cannam@127: cc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2 cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.5. What's the difference between --enable-3dnow and --enable-k7? cannam@127: cannam@127: --enable-k7 enables 3DNow! instructions on K7 processors (AMD Athlon and cannam@127: its variants). K7 support is provided by assembly routines generated by a cannam@127: special purpose compiler. As of fftw-3.2, --enable-k7 is no longer cannam@127: supported. cannam@127: cannam@127: --enable-3dnow enables generic 3DNow! support using gcc builtin functions. cannam@127: This works on earlier AMD processors, but it is not as fast as our special cannam@127: assembly routines. As of fftw-3.1, --enable-3dnow is no longer supported. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.6. What's the difference between the fma and the non-fma versions? cannam@127: cannam@127: The fma version tries to exploit the fused multiply-add instructions cannam@127: implemented in many processors such as PowerPC, ia-64, and MIPS. The two cannam@127: FFTW packages are otherwise identical. In FFTW 3.1, the fma and non-fma cannam@127: versions were merged together into a single package, and the configure cannam@127: script attempts to automatically guess which version to use. cannam@127: cannam@127: The FFTW 3.1 configure script enables fma by default on PowerPC, Itanium, cannam@127: and PA-RISC, and disables it otherwise. You can force one or the other by cannam@127: using the --enable-fma or --disable-fma flag for configure. cannam@127: cannam@127: Definitely use fma if you have a PowerPC-based system with gcc (or IBM cannam@127: xlc). This includes all GNU/Linux systems for PowerPC and the older cannam@127: PowerPC-based MacOS systems. Also use it on PA-RISC and Itanium with the cannam@127: HP/UX compiler. cannam@127: cannam@127: Definitely do not use the fma version if you have an ia-32 processor cannam@127: (Intel, AMD, MacOS on Intel, etcetera). cannam@127: cannam@127: For other architectures/compilers, the situation is not so clear. For cannam@127: example, ia-64 has the fma instruction, but gcc-3.2 appears not to exploit cannam@127: it correctly. Other compilers may do the right thing, but we have not cannam@127: tried them. Please send us your feedback so that we can update this FAQ cannam@127: entry. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.7. Which language is FFTW written in? cannam@127: cannam@127: FFTW is written in ANSI C. Most of the code, however, was automatically cannam@127: generated by a program called genfft, written in the Objective Caml cannam@127: dialect of ML. You do not need to know ML or to have an Objective Caml cannam@127: compiler in order to use FFTW. cannam@127: cannam@127: genfft is provided with the FFTW sources, which means that you can play cannam@127: with the code generator if you want. In this case, you need a working cannam@127: Objective Caml system. Objective Caml is available from the Caml web cannam@127: page. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.8. Can I call FFTW from Fortran? cannam@127: cannam@127: Yes, FFTW (versions 1.3 and higher) contains a Fortran-callable interface, cannam@127: documented in the FFTW manual. cannam@127: cannam@127: By default, FFTW configures its Fortran interface to work with the first cannam@127: compiler it finds, e.g. g77. To configure for a different, incompatible cannam@127: Fortran compiler foobar, use ./configure F77=foobar when installing FFTW. cannam@127: (In the case of g77, however, FFTW 3.x also includes an extra set of cannam@127: Fortran-callable routines with one less underscore at the end of cannam@127: identifiers, which should cover most other Fortran compilers on Linux at cannam@127: least.) cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.9. Can I call FFTW from C++? cannam@127: cannam@127: Most definitely. FFTW should compile and/or link under any C++ compiler. cannam@127: Moreover, it is likely that the C++ template class is cannam@127: bit-compatible with FFTW's complex-number format (see the FFTW manual for cannam@127: more details). cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.10. Why isn't FFTW written in Fortran/C++? cannam@127: cannam@127: Because we don't like those languages, and neither approaches the cannam@127: portability of C. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.11. How do I compile FFTW to run in single precision? cannam@127: cannam@127: On a Unix system: configure --enable-float. On a non-Unix system: edit cannam@127: config.h to #define the symbol FFTW_SINGLE (for FFTW 3.x). In both cases, cannam@127: you must then recompile FFTW. In FFTW 3, all FFTW identifiers will then cannam@127: begin with fftwf_ instead of fftw_. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 2.12. --enable-k7 does not work on x86-64 cannam@127: cannam@127: Support for --enable-k7 was discontinued in fftw-3.2. cannam@127: cannam@127: The fftw-3.1 release supports --enable-k7. This option only works on cannam@127: 32-bit x86 machines that implement 3DNow!, including the AMD Athlon and cannam@127: the AMD Opteron in 32-bit mode. --enable-k7 does not work on AMD Opteron cannam@127: in 64-bit mode. Use --enable-sse for x86-64 machines. cannam@127: cannam@127: FFTW supports 3DNow! by means of assembly code generated by a cannam@127: special-purpose compiler. It is hard to produce assembly code that works cannam@127: in both 32-bit and 64-bit mode. cannam@127: cannam@127: =============================================================================== cannam@127: cannam@127: Section 3. Using FFTW cannam@127: cannam@127: Q3.1 Why not support the FFTW 2 interface in FFTW 3? cannam@127: Q3.2 Why do FFTW 3 plans encapsulate the input/output arrays and not ju cannam@127: Q3.3 FFTW seems really slow. cannam@127: Q3.4 FFTW slows down after repeated calls. cannam@127: Q3.5 An FFTW routine is crashing when I call it. cannam@127: Q3.6 My Fortran program crashes when calling FFTW. cannam@127: Q3.7 FFTW gives results different from my old FFT. cannam@127: Q3.8 FFTW gives different results between runs cannam@127: Q3.9 Can I save FFTW's plans? cannam@127: Q3.10 Why does your inverse transform return a scaled result? cannam@127: Q3.11 How can I make FFTW put the origin (zero frequency) at the center cannam@127: Q3.12 How do I FFT an image/audio file in *foobar* format? cannam@127: Q3.13 My program does not link (on Unix). cannam@127: Q3.14 I included your header, but linking still fails. cannam@127: Q3.15 My program crashes, complaining about stack space. cannam@127: Q3.16 FFTW seems to have a memory leak. cannam@127: Q3.17 The output of FFTW's transform is all zeros. cannam@127: Q3.18 How do I call FFTW from the Microsoft language du jour? cannam@127: Q3.19 Can I compute only a subset of the DFT outputs? cannam@127: Q3.20 Can I use FFTW's routines for in-place and out-of-place matrix tra cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.1. Why not support the FFTW 2 interface in FFTW 3? cannam@127: cannam@127: FFTW 3 has semantics incompatible with earlier versions: its plans can cannam@127: only be used for a given stride, multiplicity, and other characteristics cannam@127: of the input and output arrays; these stronger semantics are necessary for cannam@127: performance reasons. Thus, it is impossible to efficiently emulate the cannam@127: older interface (whose plans can be used for any transform of the same cannam@127: size). We believe that it should be possible to upgrade most programs cannam@127: without any difficulty, however. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.2. Why do FFTW 3 plans encapsulate the input/output arrays and not just the algorithm? cannam@127: cannam@127: There are several reasons: cannam@127: cannam@127: * It was important for performance reasons that the plan be specific to cannam@127: array characteristics like the stride (and alignment, for SIMD), and cannam@127: requiring that the user maintain these invariants is error prone. cannam@127: * In most high-performance applications, as far as we can tell, you are cannam@127: usually transforming the same array over and over, so FFTW's semantics cannam@127: should not be a burden. cannam@127: * If you need to transform another array of the same size, creating a new cannam@127: plan once the first exists is a cheap operation. cannam@127: * If you need to transform many arrays of the same size at once, you cannam@127: should really use the plan_many routines in FFTW's "advanced" interface. cannam@127: * If the abovementioned array characteristics are the same, you are cannam@127: willing to pay close attention to the documentation, and you really need cannam@127: to, we provide a "new-array execution" interface to apply a plan to a cannam@127: new array. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.3. FFTW seems really slow. cannam@127: cannam@127: You are probably recreating the plan before every transform, rather than cannam@127: creating it once and reusing it for all transforms of the same size. FFTW cannam@127: is designed to be used in the following way: cannam@127: cannam@127: * First, you create a plan. This will take several seconds. cannam@127: * Then, you reuse the plan many times to perform FFTs. These are fast. cannam@127: cannam@127: If you don't need to compute many transforms and the time for the planner cannam@127: is significant, you have two options. First, you can use the cannam@127: FFTW_ESTIMATE option in the planner, which uses heuristics instead of cannam@127: runtime measurements and produces a good plan in a short time. Second, cannam@127: you can use the wisdom feature to precompute the plan; see Q3.9 `Can I cannam@127: save FFTW's plans?' cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.4. FFTW slows down after repeated calls. cannam@127: cannam@127: Probably, NaNs or similar are creeping into your data, and the slowdown is cannam@127: due to the resulting floating-point exceptions. For example, be aware cannam@127: that repeatedly FFTing the same array is a diverging process (because FFTW cannam@127: computes the unnormalized transform). cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.5. An FFTW routine is crashing when I call it. cannam@127: cannam@127: Did the FFTW test programs pass (make check, or cd tests; make bigcheck if cannam@127: you want to be paranoid)? If so, you almost certainly have a bug in your cannam@127: own code. For example, you could be passing invalid arguments (such as cannam@127: wrongly-sized arrays) to FFTW, or you could simply have memory corruption cannam@127: elsewhere in your program that causes random crashes later on. Please cannam@127: don't complain to us unless you can come up with a minimal self-contained cannam@127: program (preferably under 30 lines) that illustrates the problem. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.6. My Fortran program crashes when calling FFTW. cannam@127: cannam@127: As described in the manual, on 64-bit machines you must store the plans in cannam@127: variables large enough to hold a pointer, for example integer*8. We cannam@127: recommend using integer*8 on 32-bit machines as well, to simplify porting. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.7. FFTW gives results different from my old FFT. cannam@127: cannam@127: People follow many different conventions for the DFT, and you should be cannam@127: sure to know the ones that we use (described in the FFTW manual). In cannam@127: particular, you should be aware that the FFTW_FORWARD/FFTW_BACKWARD cannam@127: directions correspond to signs of -1/+1 in the exponent of the DFT cannam@127: definition. (*Numerical Recipes* uses the opposite convention.) cannam@127: cannam@127: You should also know that we compute an unnormalized transform. In cannam@127: contrast, Matlab is an example of program that computes a normalized cannam@127: transform. See Q3.10 `Why does your inverse transform return a scaled cannam@127: result?'. cannam@127: cannam@127: Finally, note that floating-point arithmetic is not exact, so different cannam@127: FFT algorithms will give slightly different results (on the order of the cannam@127: numerical accuracy; typically a fractional difference of 1e-15 or so in cannam@127: double precision). cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.8. FFTW gives different results between runs cannam@127: cannam@127: If you use FFTW_MEASURE or FFTW_PATIENT mode, then the algorithm FFTW cannam@127: employs is not deterministic: it depends on runtime performance cannam@127: measurements. This will cause the results to vary slightly from run to cannam@127: run. However, the differences should be slight, on the order of the cannam@127: floating-point precision, and therefore should have no practical impact on cannam@127: most applications. cannam@127: cannam@127: If you use saved plans (wisdom) or FFTW_ESTIMATE mode, however, then the cannam@127: algorithm is deterministic and the results should be identical between cannam@127: runs. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.9. Can I save FFTW's plans? cannam@127: cannam@127: Yes. Starting with version 1.2, FFTW provides the wisdom mechanism for cannam@127: saving plans; see the FFTW manual. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.10. Why does your inverse transform return a scaled result? cannam@127: cannam@127: Computing the forward transform followed by the backward transform (or cannam@127: vice versa) yields the original array scaled by the size of the array. cannam@127: (For multi-dimensional transforms, the size of the array is the product of cannam@127: the dimensions.) We could, instead, have chosen a normalization that cannam@127: would have returned the unscaled array. Or, to accomodate the many cannam@127: conventions in this matter, the transform routines could have accepted a cannam@127: "scale factor" parameter. We did not do this, however, for two reasons. cannam@127: First, we didn't want to sacrifice performance in the common case where cannam@127: the scale factor is 1. Second, in real applications the FFT is followed or cannam@127: preceded by some computation on the data, into which the scale factor can cannam@127: typically be absorbed at little or no cost. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.11. How can I make FFTW put the origin (zero frequency) at the center of its output? cannam@127: cannam@127: For human viewing of a spectrum, it is often convenient to put the origin cannam@127: in frequency space at the center of the output array, rather than in the cannam@127: zero-th element (the default in FFTW). If all of the dimensions of your cannam@127: array are even, you can accomplish this by simply multiplying each element cannam@127: of the input array by (-1)^(i + j + ...), where i, j, etcetera are the cannam@127: indices of the element. (This trick is a general property of the DFT, and cannam@127: is not specific to FFTW.) cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.12. How do I FFT an image/audio file in *foobar* format? cannam@127: cannam@127: FFTW performs an FFT on an array of floating-point values. You can cannam@127: certainly use it to compute the transform of an image or audio stream, but cannam@127: you are responsible for figuring out your data format and converting it to cannam@127: the form FFTW requires. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.13. My program does not link (on Unix). cannam@127: cannam@127: The libraries must be listed in the correct order (-lfftw3 -lm for FFTW cannam@127: 3.x) and *after* your program sources/objects. (The general rule is that cannam@127: if *A* uses *B*, then *A* must be listed before *B* in the link command.). cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.14. I included your header, but linking still fails. cannam@127: cannam@127: You're a C++ programmer, aren't you? You have to compile the FFTW library cannam@127: and link it into your program, not just #include . (Yes, this is cannam@127: really a FAQ.) cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.15. My program crashes, complaining about stack space. cannam@127: cannam@127: You cannot declare large arrays with automatic storage (e.g. via cannam@127: fftw_complex array[N]); you should use fftw_malloc (or equivalent) to cannam@127: allocate the arrays you want to transform if they are larger than a few cannam@127: hundred elements. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.16. FFTW seems to have a memory leak. cannam@127: cannam@127: After you create a plan, FFTW caches the information required to quickly cannam@127: recreate the plan. (See Q3.9 `Can I save FFTW's plans?') It also cannam@127: maintains a small amount of other persistent memory. You can deallocate cannam@127: all of FFTW's internally allocated memory, if you wish, by calling cannam@127: fftw_cleanup(), as documented in the manual. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.17. The output of FFTW's transform is all zeros. cannam@127: cannam@127: You should initialize your input array *after* creating the plan, unless cannam@127: you use FFTW_ESTIMATE: planning with FFTW_MEASURE or FFTW_PATIENT cannam@127: overwrites the input/output arrays, as described in the manual. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.18. How do I call FFTW from the Microsoft language du jour? cannam@127: cannam@127: Please *do not* ask us Windows-specific questions. We do not use Windows. cannam@127: We know nothing about Visual Basic, Visual C++, or .NET. Please find the cannam@127: appropriate Usenet discussion group and ask your question there. See also cannam@127: Q2.2 `Does FFTW run on Windows?'. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.19. Can I compute only a subset of the DFT outputs? cannam@127: cannam@127: In general, no, an FFT intrinsically computes all outputs from all inputs. cannam@127: In principle, there is something called a *pruned FFT* that can do what cannam@127: you want, but to compute K outputs out of N the complexity is in general cannam@127: O(N log K) instead of O(N log N), thus saving only a small additive factor cannam@127: in the log. (The same argument holds if you instead have only K nonzero cannam@127: inputs.) cannam@127: cannam@127: There are some specific cases in which you can get the O(N log K) cannam@127: performance benefits easily, however, by combining a few ordinary FFTs. cannam@127: In particular, the case where you want the first K outputs, where K cannam@127: divides N, can be handled by performing N/K transforms of size K and then cannam@127: summing the outputs multiplied by appropriate phase factors. For more cannam@127: details, see pruned FFTs with FFTW. cannam@127: cannam@127: There are also some algorithms that compute pruned transforms cannam@127: *approximately*, but they are beyond the scope of this FAQ. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 3.20. Can I use FFTW's routines for in-place and out-of-place matrix transposition? cannam@127: cannam@127: You can use the FFTW guru interface to create a rank-0 transform of vector cannam@127: rank 2 where the vector strides are transposed. (A rank-0 transform is cannam@127: equivalent to a 1D transform of size 1, which. just copies the input into cannam@127: the output.) Specifying the same location for the input and output makes cannam@127: the transpose in-place. cannam@127: cannam@127: For double-valued data stored in row-major format, plan creation looks cannam@127: like this: cannam@127: cannam@127: fftw_plan plan_transpose(int rows, int cols, double *in, double *out) cannam@127: { cannam@127: const unsigned flags = FFTW_ESTIMATE; /* other flags are possible */ cannam@127: fftw_iodim howmany_dims[2]; cannam@127: cannam@127: howmany_dims[0].n = rows; cannam@127: howmany_dims[0].is = cols; cannam@127: howmany_dims[0].os = 1; cannam@127: cannam@127: howmany_dims[1].n = cols; cannam@127: howmany_dims[1].is = 1; cannam@127: howmany_dims[1].os = rows; cannam@127: cannam@127: return fftw_plan_guru_r2r(/*rank=*/ 0, /*dims=*/ NULL, cannam@127: /*howmany_rank=*/ 2, howmany_dims, cannam@127: in, out, /*kind=*/ NULL, flags); cannam@127: } cannam@127: (This entry was written by Rhys Ulerich.) cannam@127: cannam@127: =============================================================================== cannam@127: cannam@127: Section 4. Internals of FFTW cannam@127: cannam@127: Q4.1 How does FFTW work? cannam@127: Q4.2 Why is FFTW so fast? cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 4.1. How does FFTW work? cannam@127: cannam@127: The innovation (if it can be so called) in FFTW consists in having a cannam@127: variety of composable *solvers*, representing different FFT algorithms and cannam@127: implementation strategies, whose combination into a particular *plan* for cannam@127: a given size can be determined at runtime according to the characteristics cannam@127: of your machine/compiler. This peculiar software architecture allows FFTW cannam@127: to adapt itself to almost any machine. cannam@127: cannam@127: For more details (albeit somewhat outdated), see the paper "FFTW: An cannam@127: Adaptive Software Architecture for the FFT", by M. Frigo and S. G. cannam@127: Johnson, *Proc. ICASSP* 3, 1381 (1998), also available at the FFTW web cannam@127: page. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 4.2. Why is FFTW so fast? cannam@127: cannam@127: This is a complex question, and there is no simple answer. In fact, the cannam@127: authors do not fully know the answer, either. In addition to many small cannam@127: performance hacks throughout FFTW, there are three general reasons for cannam@127: FFTW's speed. cannam@127: cannam@127: * FFTW uses a variety of FFT algorithms and implementation styles that cannam@127: can be arbitrarily composed to adapt itself to a machine. See Q4.1 `How cannam@127: does FFTW work?'. cannam@127: * FFTW uses a code generator to produce highly-optimized routines for cannam@127: computing small transforms. cannam@127: * FFTW uses explicit divide-and-conquer to take advantage of the memory cannam@127: hierarchy. cannam@127: cannam@127: For more details (albeit somewhat outdated), see the paper "FFTW: An cannam@127: Adaptive Software Architecture for the FFT", by M. Frigo and S. G. cannam@127: Johnson, *Proc. ICASSP* 3, 1381 (1998), available along with other cannam@127: references at the FFTW web page. cannam@127: cannam@127: =============================================================================== cannam@127: cannam@127: Section 5. Known bugs cannam@127: cannam@127: Q5.1 FFTW 1.1 crashes in rfftwnd on Linux. cannam@127: Q5.2 The MPI transforms in FFTW 1.2 give incorrect results/leak memory. cannam@127: Q5.3 The test programs in FFTW 1.2.1 fail when I change FFTW to use sin cannam@127: Q5.4 The test program in FFTW 1.2.1 fails for n > 46340. cannam@127: Q5.5 The threaded code fails on Linux Redhat 5.0 cannam@127: Q5.6 FFTW 2.0's rfftwnd fails for rank > 1 transforms with a final dime cannam@127: Q5.7 FFTW 2.0's complex transforms give the wrong results with prime fa cannam@127: Q5.8 FFTW 2.1.1's MPI test programs crash with MPICH. cannam@127: Q5.9 FFTW 2.1.2's multi-threaded transforms don't work on AIX. cannam@127: Q5.10 FFTW 2.1.2's complex transforms give incorrect results for large p cannam@127: Q5.11 FFTW 2.1.3's multi-threaded transforms don't give any speedup on S cannam@127: Q5.12 FFTW 2.1.3 crashes on AIX. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.1. FFTW 1.1 crashes in rfftwnd on Linux. cannam@127: cannam@127: This bug was fixed in FFTW 1.2. There was a bug in rfftwnd causing an cannam@127: incorrect amount of memory to be allocated. The bug showed up in Linux cannam@127: with libc-5.3.12 (and nowhere else that we know of). cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.2. The MPI transforms in FFTW 1.2 give incorrect results/leak memory. cannam@127: cannam@127: These bugs were corrected in FFTW 1.2.1. The MPI transforms (really, just cannam@127: the transpose routines) in FFTW 1.2 had bugs that could cause errors in cannam@127: some situations. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.3. The test programs in FFTW 1.2.1 fail when I change FFTW to use single precision. cannam@127: cannam@127: This bug was fixed in FFTW 1.3. (Older versions of FFTW did work in cannam@127: single precision, but the test programs didn't--the error tolerances in cannam@127: the tests were set for double precision.) cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.4. The test program in FFTW 1.2.1 fails for n > 46340. cannam@127: cannam@127: This bug was fixed in FFTW 1.3. FFTW 1.2.1 produced the right answer, but cannam@127: the test program was wrong. For large n, n*n in the naive transform that cannam@127: we used for comparison overflows 32 bit integer precision, breaking the cannam@127: test. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.5. The threaded code fails on Linux Redhat 5.0 cannam@127: cannam@127: We had problems with glibc-2.0.5. The code should work with glibc-2.0.7. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.6. FFTW 2.0's rfftwnd fails for rank > 1 transforms with a final dimension >= 65536. cannam@127: cannam@127: This bug was fixed in FFTW 2.0.1. (There was a 32-bit integer overflow cannam@127: due to a poorly-parenthesized expression.) cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.7. FFTW 2.0's complex transforms give the wrong results with prime factors 17 to 97. cannam@127: cannam@127: There was a bug in the complex transforms that could cause incorrect cannam@127: results under (hopefully rare) circumstances for lengths with cannam@127: intermediate-size prime factors (17-97). This bug was fixed in FFTW cannam@127: 2.1.1. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.8. FFTW 2.1.1's MPI test programs crash with MPICH. cannam@127: cannam@127: This bug was fixed in FFTW 2.1.2. The 2.1/2.1.1 MPI test programs crashed cannam@127: when using the MPICH implementation of MPI with the ch_p4 device (TCP/IP); cannam@127: the transforms themselves worked fine. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.9. FFTW 2.1.2's multi-threaded transforms don't work on AIX. cannam@127: cannam@127: This bug was fixed in FFTW 2.1.3. The multi-threaded transforms in cannam@127: previous versions didn't work with AIX's pthreads implementation, which cannam@127: idiosyncratically creates threads in detached (non-joinable) mode by cannam@127: default. cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.10. FFTW 2.1.2's complex transforms give incorrect results for large prime sizes. cannam@127: cannam@127: This bug was fixed in FFTW 2.1.3. FFTW's complex-transform algorithm for cannam@127: prime sizes (in versions 2.0 to 2.1.2) had an integer overflow problem cannam@127: that caused incorrect results for many primes greater than 32768 (on cannam@127: 32-bit machines). (Sizes without large prime factors are not affected.) cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.11. FFTW 2.1.3's multi-threaded transforms don't give any speedup on Solaris. cannam@127: cannam@127: This bug was fixed in FFTW 2.1.4. (By default, Solaris creates threads cannam@127: that do not parallelize over multiple processors, so one has to request cannam@127: the proper behavior specifically.) cannam@127: cannam@127: ------------------------------------------------------------------------------- cannam@127: cannam@127: Question 5.12. FFTW 2.1.3 crashes on AIX. cannam@127: cannam@127: The FFTW 2.1.3 configure script picked incorrect compiler flags for the cannam@127: xlc compiler on newer IBM processors. This is fixed in FFTW 2.1.4. cannam@127: