Subversion Repositories shark

\comment This is the source for the FFTW FAQ list, in

\comment the Bizarre Format With No Name.  It is turned into Lout

\comment input, HTML, plain ASCII and an Info document by a Perl script.

\comment

\comment The format and scripts come from the Linux FAQ, by

\comment Ian Jackson.

\set brieftitle FFTW FAQ

\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>

\set authormail fftw@theory.lcs.mit.edu

\set title      FFTW Frequently Asked Questions with Answers

\set copyholder Massachusetts Institute of Technology

\call-html startup html.refs

\copyto ASCII

            FFTW FREQUENTLY ASKED QUESTIONS WITH ANSWERS

                            `date '+%d %h %Y'`

			     Matteo Frigo

			   Steven G. Johnson

		       <fftw@theory.lcs.mit.edu>

\endcopy

\copyto INFO

START-INFO-DIR-ENTRY

* FFTW FAQ: (fftw-faq). FFTW Frequently Asked Questions with Answers.

END-INFO-DIR-ENTRY

File: $prefix.info, Node: Top, Next: Question 1.1, Up: (dir)

            FFTW FREQUENTLY ASKED QUESTIONS WITH ANSWERS

                            `date '+%d %h %Y'`

			     Matteo Frigo

			   Steven G. Johnson

		       <fftw@theory.lcs.mit.edu>

\endcopy

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.

\section  Index

\index

\comment ######################################################################

\section  Introduction and General Information

\question 26aug:whatisfftw  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 26aug:whereisfftw  How do I obtain FFTW?

FFTW can be found at \docref{the FFTW web page\}.  You can also

retrieve it from \ftpon theory.lcs.mit.edu in \ftpin /pub/fftw.

\question 26aug:isfftwfree  Is FFTW free software?

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

sense defined by the Free Software Foundation (see \docref{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 10apr:nonfree  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.

\comment ######################################################################

\section  Installing FFTW

\question 26aug:systems  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 \qref runOnDOS and

\qref compilerCrashes.)

\question 26aug:runOnDOS  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 \docref{FFTW Windows

installation notes\} and \qref compilerCrashes

\question 26aug:compilerCrashes  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,

\courier{gcc 2.7.2\}, Sun's \courier{SC4.0\}, IBM's \courier{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 \courier{-xO5\} option in Sun's

\courier{SC4.0\} C compiler.

\question 26aug:solarisSucks FFTW does not compile on Solaris, complaining about \courier{const\}.

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

might get error messages from \courier{make\} such as

\courier{"./fftw.h", line 88: warning: const is a keyword in ANSI C\}

This is the case when the \courier{configure\} script reports that

\courier{const\} does not work:

\courier{checking for working const... (cached) no\}

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

\courier{/opt/SUNWspro/SC4.2/bin/cc\} and \courier{/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 \courier{cc\}

is used.

To know whether your compiler is the right one,  type

\courier{cc -V\}.  If the compiler prints ``\courier{ucbcc\}'',

as in

\courier{ucbcc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2\}

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

\courier{cc: WorkShop Compilers 4.2 30 Oct 1996 C 4.2\}

\question 26aug:languages  Which language is FFTW written in?

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

automatically generated by a program called \courier{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.

\courier{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 \ftpon ftp.inria.fr in the directory \ftpin /lang/caml-light.

\question 26aug:fortran  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 26aug:cplusplus  Can I call FFTW from C++?

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

\question 26aug:whynotfortran  Why isn't FFTW written in FORTRAN/C++?

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

portability of C.

\question 29mar:singleprec How do I compile FFTW to run in single precision?

On a Unix system: \courier{configure --enable-float\}.  On a non-Unix

system: edit \courier{fftw/fftw.h\} to \courier{#define\} the symbol

\courier{FFTW_ENABLE_FLOAT\}.  In both cases, you must then recompile

FFTW.

\comment ######################################################################

\section  Using FFTW

\question 25may:slow 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:

\call startlist

\call item

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

\call item

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

\call endlist

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

\courier{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 \qref savePlans

\question 24mar:conventions 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

\courier{FFTW_FORWARD\}/\courier{FFTW_BACKWARD\} directions correspond

to signs of -1/+1 in the exponent of the DFT definition.

(\italic{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 \qref whyscaled.

\question 26aug:savePlans Can I save FFTW's plans?

Yes. Starting with version 1.2, FFTW provides the

\courier{wisdom\} mechanism for saving plans.  See \qref wisdom

and the FFTW manual.

\question 14sep:whyscaled 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 02dec:centerorigin 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 08may:imageaudio How do I FFT an image/audio file in \italic{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 09apr:linkfails My program does not link (on Unix).

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

FFTW manual (e.g. \courier{-lrfftw -lfftw -lm\}).  Also, note that the

libraries must be listed after your program sources/objects.  (The

general rule is that if \italic{A\} uses \italic{B\}, then \italic{A\}

must be listed before \italic{B\} in the link command.).  For example,

switching the order to \courier{-lfftw -lrfftw -lm\} will fail.

\comment ######################################################################

\section  Internals of FFTW

\question 26aug:howworks  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 \italic{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 \docref{the FFTW

web page\}.  See also "FFTW: An Adaptive Software Architecture for the

FFT", in ICASSP '98.

\question 26aug:whyfast 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.

\call startlist

\call item

	FFTW uses an internal interpreter to adapt itself to

a machine.  See \qref howworks.

\call item

	FFTW uses a code generator to produce highly-optimized

routines for computing small transforms.

\call item

	FFTW uses explicit divide-and-conquer to take advantage

of the memory hierarchy.

\call endlist

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 \docref{the FFTW web page\}.

\question 26aug:wisdom What is this \courier{wisdom\} thing?

\courier{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 \courier{wisdom\} for later use.

\question 26aug:whywisdom Why do you use \courier{wisdom\}? I just wanted to save a plan.

\courier{wisdom\} could be implemented with less effort than a general

plan-saving mechanism would have required.  In addition,

\courier{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, \courier{wisdom\} does more things with less effort, and

seemed like The Right Thing to do.

\comment ######################################################################

\section  Known bugs

\question 27aug:rfftwndbug  FFTW 1.1 crashes in rfftwnd on Linux.

This bug was fixed in FFTW 1.2.  There was a bug in \courier{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 15oct:fftwmpibug 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 05nov:testsingbug 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 24mar:teststoobig 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 24aug:linuxthreads 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 26sep:bigrfftwnd 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 26mar:primebug 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 05apr:mpichbug 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 \courier{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.)

\comment Here it ends!