This chapter provides a complete reference for all FFTW functions.
Programs using FFTW should be linked with -lfftw -lm
.
By including <fftw.h>
, you will have access to the following
definitions:
typedef double FFTW_REAL; typedef struct { FFTW_REAL re, im; } FFTW_COMPLEX; #define c_re(c) ((c).re) #define c_im(c) ((c).im)
All FFTW operations are performed on the FFTW_COMPLEX
data type.
The two macros c_re
and c_im
retrieve, respectively,
the real and imaginary parts of a complex number.
Users who wish to work in single precision rather than double precision
merely need to change the definition of FFTW_REAL
from double
to float
in fftw.h
and then recompile the library.
#include <fftw.h> fftw_plan fftw_create_plan(int n, fftw_direction dir, int flags);
The function fftw_create_plan
creates a plan, which is
a data structure containing all the information that fftw
needs in order to compute the 1D Fourier Transform. You can
create as many plans as you need, but only one plan for a given
array size is required (a plan can be reused many times).
fftw_create_plan
returns a valid plan, or NULL
if, for some reason, the plan can't be created. In the
default installation, this can't happen, but it is possible
to configure FFTW in such a way that some input sizes are
forbidden, and FFTW cannot create a plan.
n
is the size of the transform. It can be
any positive integer.
dir
is the sign of the exponent in the formula that
defines the Fourier Transform. It can be or .
The aliases FFTW_FORWARD
and FFTW_BACKWARD
are provided, where FFTW_FORWARD
stands for .
flags
is a boolean OR (`|') of zero or more of the following:
FFTW_MEASURE
: this flag tells FFTW to find the optimal plan by
actually computing several FFTs and measuring their
execution time. Depending on the installation, this can take some
time.(2)
FFTW_ESTIMATE
: do not run any FFT and provide a "reasonable"
plan (on a RISC processor with many registers). If neither
FFTW_ESTIMATE
nor FFTW_MEASURE
is provided, the default is
FFTW_ESTIMATE
.
FFTW_OUT_OF_PLACE
: produce a plan assuming that the input
and output arrays will be distinct (this is the default).
FFTW_IN_PLACE
: produce a plan assuming that you want the output
in the input array. The algorithm used is not necessarily in place:
FFTW is able to compute true in-place transforms only for small values
of n
. If FFTW is not able to compute the transform in-place, it
will allocate a temporary array (unless you provide one yourself),
compute the transform out of place, and copy the result back.
The in-place option is mainly provided for people who want to write
their own in-place multi-dimensional Fourier Transform, using FFTW as a
base. For example, consider a three-dimensional n * n * n
transform. An out-of-place algorithm will need another array (which may
be huge). However, FFTW can compute the in-place transform along
each dimension using only a temporary array of size n
.
Moreover, if FFTW happens to be able to compute the transform truly
in-place, no temporary array and no copying are needed. As distributed,
FFTW `knows' how to compute in-place transforms of size 1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 32 and 64.
The default mode of operation is FFTW_OUT_OF_PLACE
.
#include <fftw.h> fftwnd_plan fftwnd_create_plan(int rank, const int *n, fftw_direction dir, int flags); fftwnd_plan fftw2d_create_plan(int nx, int ny, fftw_direction dir, int flags); fftwnd_plan fftw3d_create_plan(int nx, int ny, int nz, fftw_direction dir, int flags);
The function fftwnd_create_plan
creates a plan, which is a data
structure containing all the information that fftwnd
needs in
order to compute a multi-dimensional Fourier Transform. You can create
as many plans as you need, but only one plan for a given array size is
required (a plan can be reused many times). The functions
fftw2d_create_plan
and fftw3d_create_plan
are optional,
alternative interfaces to fftwnd_create_plan
for two and three
dimensions, respectively.
fftwnd_create_plan
returns a valid plan, or NULL
if, for
some reason, the plan can't be created. This can happen if memory runs
out or if the arguments are invalid in some way (e.g. if rank
<
0).
rank
is the dimensionality of the arrays to be transformed. It
can be any non-negative integer.
n
is a pointer to an array of rank
integers, giving the
size of each dimension of the arrays to be transformed. These sizes,
which must be positive integers, correspond to the dimensions of
row-major arrays--i.e. n[0] is the size of the dimension whose indices
vary most slowly, and so on. (See section Multi-dimensional Array Format, for
more information.)
nx
and ny
in fftw2d_create_plan
are positive
integers specifying the dimensions of the rank 2 array to be
transformed. i.e. they specify that the transform will operate on
nx x ny
arrays in row-major order.
nx
, ny
and nz
in fftw3d_create_plan
are
positive integers specifying the dimensions of the rank 3 array to be
transformed. i.e. they specify that the transform will operate on
nx x ny x nz
arrays in row-major order.
dir
is the sign of the exponent in the formula that defines the
Fourier Transform. It can be or . The aliases
FFTW_FORWARD
and FFTW_BACKWARD
are provided, where
FFTW_FORWARD
stands for .
flags
is a boolean OR (`|') of zero or more of the following:
FFTW_MEASURE
: this flag tells FFTW to find the optimal plan by
actually computing several FFTs and measuring their execution
time.
FFTW_ESTIMATE
: do not run any FFT and provide a "reasonable"
plan (on a RISC processor with many registers). If neither
FFTW_ESTIMATE
nor FFTW_MEASURE
is provided, the default is
FFTW_ESTIMATE
.
FFTW_OUT_OF_PLACE
: produce a plan assuming that the input
and output arrays will be distinct (this is the default).
FFTW_IN_PLACE
: produce a plan assuming that you want to perform
the transform in-place. (Unlike the one-dimensional transform, this
"really"(3) performs the
transform in-place.) Note that, if you want to perform in-place
transforms, you must use a plan created with this option.
The default mode of operation is FFTW_OUT_OF_PLACE
.
#include <fftw.h> void fftw(fftw_plan plan, int howmany, FFTW_COMPLEX *in, int istride, int idist, FFTW_COMPLEX *out, int ostride, int odist);
The function fftw
computes the one-dimensional Fourier Transform,
using a plan created by fftw_create_plan
(See section Plan Creation for One-dimensional Transforms.)
plan
is the plan created by fftw_create_plan
(See section Plan Creation for One-dimensional Transforms.)
howmany
is the number of transforms fftw
will compute.
It is faster to tell FFTW to compute many transforms, instead of
simply calling fftw
many times.
in
, istride
and idist
describe the input array(s).
There are howmany
input arrays; the first one is pointed to by
in
, the second one is pointed to by in + idist
, and so on,
up to in + (howmany - 1) * idist
. Each input array consists of
complex numbers (See section Complex Numbers), which are not necessarily
contiguous in memory. Specifically, in[0]
is the first element
of the first array, in[istride]
is the second element of the
first array, and so on. In general, the i
-th element of the
j
-th input array will be in position in[i * istride + j *
idist]
.
out
, ostride
and odist
describe the output
array(s). The format is the same as for the input array.
plan
specifies an in-place transform, ostride
and
odist
are always ignored. If out
is NULL
,
out
is ignored, too. Otherwise, out
is interpreted as a
pointer to an array of n
complex numbers, that FFTW will use as
temporary space to perform the in-place computation. In this case,
out
must be an ordinary array whose elements are contiguous in
memory (no striding).
#include <fftw.h> void fftwnd(fftwnd_plan plan, int howmany, FFTW_COMPLEX *in, int istride, int idist, FFTW_COMPLEX *out, int ostride, int odist);
The function fftwnd
computes the multi-dimensional Fourier Transform,
using a plan created by fftwnd_create_plan
(See section Plan Creation for Multi-dimensional Transforms.) (Note that the plan
determines the rank and dimensions of the array to be transformed.)
plan
is the plan created by fftwnd_create_plan
.
(See section Plan Creation for Multi-dimensional Transforms.) (In the case of two and
three-dimensional transforms, it could also have been created by
fftw2d_create_plan
or fftw3d_create_plan
, respectively.)
howmany
is the number of transforms fftw
will compute.
in
, istride
and idist
describe the input array(s).
There are howmany
input arrays; the first one is pointed to by
in
, the second one is pointed to by in + idist
, and so on,
up to in + (howmany - 1) * idist
. Each input array consists of
complex numbers (See section Complex Numbers), stored in row-major format
(See section Multi-dimensional Array Format), which are not necessarily
contiguous in memory. Specifically, in[0]
is the first element
of the first array, in[istride]
is the second element of the
first array, and so on. In general, the i
-th element of the
j
-th input array will be in position in[i * istride + j *
idist]
. Note that, here, i
refers to an index into the row-major
format for the multi-dimensional array, rather than an index in any
particular dimension.
FFTW_IN_PLACE
option, the transform is
computed in-place--the output is returned in the in
array, using
the same strides, etcetera, as were used in the input.
out
, ostride
and odist
describe the output array(s).
The format is the same as for the input array.
FFTW_IN_PLACE
option.
#include <fftw.h> void fftw_destroy_plan(fftw_plan plan);
The function fftw_destroy_plan
frees the plan plan
, and
releases all the memory associated with it. After destruction, a plan
is no longer valid.
#include <fftw.h> void fftwnd_destroy_plan(fftwnd_plan plan);
The function fftwnd_destroy_plan
frees the plan plan
,
and releases all the memory associated with it. After destruction,
a plan is no longer valid.
#include <fftw.h> extern void *(*fftw_malloc_hook) (size_t n); extern void (*fftw_free_hook) (void *p);
FFTW needs some memory for internal use. It ordinarily calls
malloc
and free
to allocate and release memory; if
malloc
fails, FFTW prints an error message and exits. This
behavior may be undesirable in some applications; consequently, FFTW
provide means by which you can install your own memory allocator and
take whatever error-correcting action you find appropriate. The
variables fftw_malloc_hook
and fftw_free_hook
are pointers
to functions, and they are normally NULL
. If you set those
variables to point to another function, FFTW will use your function
instead of its own internal malloc
and free
.
fftw_malloc_hook
must point to a malloc
-like function,
and
fftw_free_hook
must point to a free
-like function.