159
This manual documents version 2.1.3 of FFTW, the *Fastest Fourier
160
Transform in the West*. FFTW is a comprehensive collection of fast C
158
This manual documents version 2.1.5 of FFTW, the _Fastest Fourier
159
Transform in the West_. FFTW is a comprehensive collection of fast C
161
160
routines for computing the discrete Fourier transform (DFT) in one or
162
161
more dimensions, of both real and complex data, and of arbitrary input
163
162
size. FFTW also includes parallel transforms for both shared- and
164
163
distributed-memory systems. We assume herein that the reader is already
165
164
familiar with the properties and uses of the DFT that are relevant to
166
165
her application. Otherwise, see e.g. `The Fast Fourier Transform' by
167
E. O. Brigham (Prentice-Hall, Englewood Cliffs, NJ, 1974).
168
Our web page (http://www.fftw.org) also has links to FFT-related
166
E. O. Brigham (Prentice-Hall, Englewood Cliffs, NJ, 1974). Our web
167
page (http://www.fftw.org) also has links to FFT-related information
171
170
FFTW is usually faster (and sometimes much faster) than all other
172
171
freely-available Fourier transform programs found on the Net. For
173
172
transforms whose size is a power of two, it compares favorably with the
174
173
FFT codes in Sun's Performance Library and IBM's ESSL library, which are
175
174
targeted at specific machines. Moreover, FFTW's performance is
176
*portable*. Indeed, FFTW is unique in that it automatically adapts
175
_portable_. Indeed, FFTW is unique in that it automatically adapts
177
176
itself to your machine, your cache, the size of your memory, the number
178
177
of registers, and all the other factors that normally make it impossible
179
178
to optimize a program for more than one machine. An extensive
180
179
comparison of FFTW's performance with that of other Fourier transform
181
codes has been made. The results are available on the Web at
182
the benchFFT home page (http://theory.lcs.mit.edu/~benchfft).
180
codes has been made. The results are available on the Web at the
181
benchFFT home page (http://theory.lcs.mit.edu/~benchfft).
184
183
In order to use FFTW effectively, you need to understand one basic
185
184
concept of FFTW's internal structure. FFTW does not used a fixed
219
218
with a shared-memory implementation on top of POSIX (and similar)
220
219
threads, as well as a distributed-memory implementation based on MPI.
221
220
We also provide an experimental parallel implementation written in Cilk,
222
*the superior programming tool of choice for discriminating hackers*
223
(Olin Shivers). (See the Cilk home page (http://supertech.lcs.mit.edu/cilk).)
221
_the superior programming tool of choice for discriminating hackers_
222
(Olin Shivers). (See the Cilk home page
223
(http://supertech.lcs.mit.edu/cilk).)
225
225
For more information regarding FFTW, see the paper, "The Fastest
226
226
Fourier Transform in the West," by M. Frigo and S. G. Johnson, which is
266
266
This chapter describes the basic usage of FFTW, i.e., how to compute
267
267
the Fourier transform of a single array. This chapter tells the truth,
268
but not the *whole* truth. Specifically, FFTW implements additional
268
but not the _whole_ truth. Specifically, FFTW implements additional
269
269
routines and flags, providing extra functionality, that are not
270
270
documented here. *Note FFTW Reference::, for more complete information.
271
271
(Note that you need to compile and install FFTW before you can use it in
366
366
floating-point components. The `in' and `out' arrays should have the
367
367
length specified when the plan was created. An alternative function,
368
368
`fftw', allows you to efficiently perform multiple and/or strided
369
transforms (*note FFTW Reference::.).
369
transforms (*note FFTW Reference::).
371
371
The DFT results are stored in-order in the array `out', with the
372
372
zero-frequency (DC) component in `out[0]'. The array `in' is not
493
493
rfftw_plan rfftw_create_plan(int n, fftw_direction dir, int flags);
495
`n' is the length of the *real* array in the transform (even for
495
`n' is the length of the _real_ array in the transform (even for
496
496
halfcomplex-to-real transforms), and can be any positive integer
497
497
(although sizes with small factors are transformed more efficiently).
498
498
`dir' is either `FFTW_REAL_TO_COMPLEX' or `FFTW_COMPLEX_TO_REAL'. The
639
639
dimension is even and one if it is odd. That is, the last dimension of
640
640
the real data must physically contain 2 * (nd/2+1) `fftw_real' values
641
641
(exactly enough to hold the complex data). This physical array size
642
does not, however, change the *logical* array size--only nd values are
642
does not, however, change the _logical_ array size--only nd values are
643
643
actually stored in the last dimension, and nd is the last dimension
644
644
passed to `rfftwnd_create_plan'.
646
646
For example, consider the transform of a two-dimensional real array
647
647
of size `nx' by `ny'. The output of the `rfftwnd' transform is a
648
two-dimensional real array of size `nx' by `ny/2+1', where the `y'
648
two-dimensional complex array of size `nx' by `ny/2+1', where the `y'
649
649
dimension has been cut nearly in half because of redundancies in the
650
650
output. Because `fftw_complex' is twice the size of `fftw_real', the
651
651
output array is slightly bigger than the input array. Thus, if we want
652
to compute the transform in place, we must *pad* the input array so
652
to compute the transform in place, we must _pad_ the input array so
653
653
that it is of size `nx' by `2*(ny/2+1)'. If `ny' is even, then there
654
654
are two padding elements at the end of each row (which need not be
655
655
initialized, as they are only used for output).
785
785
Readers from the Fortran world are used to arrays stored in
786
786
"column-major" order (sometimes called "Fortran order"). This is
787
787
essentially the exact opposite of row-major order in that, here, the
788
*first* dimension's index varies most quickly.
788
_first_ dimension's index varies most quickly.
790
790
If you have an array stored in column-major order and wish to
791
791
transform it using `fftwnd', it is quite easy to do. When creating the
792
792
plan, simply pass the dimensions of the array to `fftwnd_create_plan' in
793
*reverse order*. For example, if your array is a rank three `N x M x
793
_reverse order_. For example, if your array is a rank three `N x M x
794
794
L' matrix in column-major order, you should pass the dimensions of the
795
795
array as if it were an `L x M x N' matrix (which it is, from the
796
796
perspective of `fftwnd'). This is done for you automatically by the
797
FFTW Fortran wrapper routines (*note Calling FFTW from Fortran::.).
797
FFTW Fortran wrapper routines (*note Calling FFTW from Fortran::).
800
800
File: fftw.info, Node: Static Arrays in C, Next: Dynamic Arrays in C, Prev: Column-major Format, Up: Multi-dimensional Array Format
803
803
------------------
805
805
Multi-dimensional arrays declared statically (that is, at compile
806
time, not necessarily with the `static' keyword) in C are *already* in
806
time, not necessarily with the `static' keyword) in C are _already_ in
807
807
row-major order. You don't have to do anything special to transform
808
808
them. (*Note Complex Multi-dimensional Transforms Tutorial::, for an
809
809
example of this sort of code.)
846
846
----------------------------------
848
848
A different method for allocating multi-dimensional arrays in C is
849
often suggested that is incompatible with `fftwnd': *using it will
850
cause FFTW to die a painful death*. We discuss the technique here,
849
often suggested that is incompatible with `fftwnd': _using it will
850
cause FFTW to die a painful death_. We discuss the technique here,
851
851
however, because it is so commonly known and used. This method is to
852
852
create arrays of pointers of arrays of pointers of ...etcetera. For
853
853
example, the analogue in this method to the example above is:
added
removed
doc/fftw.info-1
