Subversion Repositories shark

            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.)