fftw_3.html

FFTW, a collection of fast C routines to compute the Discrete Fourier Transform in one or more dime

<P>
The function <CODE>fftw</CODE> computes the one-dimensional Fourier transform,
using a plan created by <CODE>fftw_create_plan</CODE> (See Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>.)  The function
<CODE>fftw_one</CODE> provides a simplified interface for the common case of
single input array of stride 1.
<A NAME="IDX120"></A>



<H4>Arguments</H4>

<UL>
<LI>

<CODE>plan</CODE> is the plan created by <CODE>fftw_create_plan</CODE>
(see Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>).

<LI>

<CODE>howmany</CODE> is the number of transforms <CODE>fftw</CODE> will compute.
It is faster to tell FFTW to compute many transforms, instead of
simply calling <CODE>fftw</CODE> many times.

<LI>

<CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s).
There are <CODE>howmany</CODE> input arrays; the first one is pointed to by
<CODE>in</CODE>, the second one is pointed to by <CODE>in + idist</CODE>, and so on,
up to <CODE>in + (howmany - 1) * idist</CODE>.  Each input array consists of
complex numbers (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>), which are not necessarily
contiguous in memory.  Specifically, <CODE>in[0]</CODE> is the first element
of the first array, <CODE>in[istride]</CODE> is the second element of the
first array, and so on.  In general, the <CODE>i</CODE>-th element of the
<CODE>j</CODE>-th input array will be in position <CODE>in[i * istride + j *
idist]</CODE>.

<LI>

<CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output
array(s).  The format is the same as for the input array.


<UL>
<LI><EM>In-place transforms</EM>:

<A NAME="IDX121"></A>
If the <CODE>plan</CODE> specifies an in-place transform, <CODE>ostride</CODE> and
<CODE>odist</CODE> are always ignored.  If <CODE>out</CODE> is <CODE>NULL</CODE>,
<CODE>out</CODE> is ignored, too.  Otherwise, <CODE>out</CODE> is interpreted as a
pointer to an array of <CODE>n</CODE> complex numbers, that FFTW will use as
temporary space to perform the in-place computation.  <CODE>out</CODE> is used
as scratch space and its contents destroyed.  In this case, <CODE>out</CODE>
must be an ordinary array whose elements are contiguous in memory (no
striding).
</UL>

</UL>

<P>
The function <CODE>fftw_one</CODE> transforms a single, contiguous input array
to a contiguous output array.  By definition, the call

<PRE>
fftw_one(plan, in, out)
</PRE>

<P>
is equivalent to

<PRE>
fftw(plan, 1, in, 1, 0, out, 1, 0)
</PRE>



<H3><A NAME="SEC22">Destroying a One-dimensional Plan</A></H3>


<PRE>
#include &#60;fftw.h&#62;

void fftw_destroy_plan(fftw_plan plan);
</PRE>

<P>
<A NAME="IDX122"></A>


<P>
The function <CODE>fftw_destroy_plan</CODE> frees the plan <CODE>plan</CODE> and
releases all the memory associated with it.  After destruction, a plan
is no longer valid.




<H3><A NAME="SEC23">What FFTW Really Computes</A></H3>
<P>
<A NAME="IDX123"></A>
In this section, we define precisely what FFTW computes.  Please be
warned that different authors and software packages might employ
different conventions than FFTW does.


<P>
The forward transform of a complex array X of size
n computes an array Y, where
<center><IMG SRC="equation-1.gif" ALIGN="top"></center>


<P>
The backward transform computes
<center><IMG SRC="equation-2.gif" ALIGN="top"></center>


<P>
<A NAME="IDX124"></A>
FFTW computes an unnormalized transform, that is, the equation
IFFT(FFT(X)) = n X holds.  In other words, applying the forward
and then the backward transform will multiply the input by n.


<P>
<A NAME="IDX125"></A>
An <CODE>FFTW_FORWARD</CODE> transform corresponds to a sign of -1 in
the exponent of the DFT.  Note also that we use the standard
"in-order" output ordering--the k-th output corresponds to the
frequency k/n (or k/T, where T is your total
sampling period).  For those who like to think in terms of positive and
negative frequencies, this means that the positive frequencies are
stored in the first half of the output and the negative frequencies are
stored in backwards order in the second half of the output.  (The
frequency -k/n is the same as the frequency (n-k)/n.)




<H2><A NAME="SEC24">Multi-dimensional Transforms Reference</A></H2>
<P>
<A NAME="IDX126"></A>
<A NAME="IDX127"></A>
The multi-dimensional complex routines are generally prefixed with
<CODE>fftwnd_</CODE>.  Programs using FFTWND should be linked with <CODE>-lfftw
-lm</CODE> on Unix systems, or with the FFTW and standard math libraries in
general.
<A NAME="IDX128"></A>




<H3><A NAME="SEC25">Plan Creation for Multi-dimensional Transforms</A></H3>


<PRE>
#include &#60;fftw.h&#62;

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

fftwnd_plan fftwnd_create_plan_specific(int rank, const int *n,
                                        fftw_direction dir,
                                        int flags,
                                        fftw_complex *in, int istride,
                                        fftw_complex *out, int ostride);

fftwnd_plan fftw2d_create_plan_specific(int nx, int ny,
                                        fftw_direction dir,
                                        int flags,
                                        fftw_complex *in, int istride,
                                        fftw_complex *out, int ostride);

fftwnd_plan fftw3d_create_plan_specific(int nx, int ny, int nz,
                                        fftw_direction dir, int flags,
                                        fftw_complex *in, int istride,
                                        fftw_complex *out, int ostride);
</PRE>

<P>
<A NAME="IDX129"></A>
<A NAME="IDX130"></A>
<A NAME="IDX131"></A>
<A NAME="IDX132"></A>
<A NAME="IDX133"></A>
<A NAME="IDX134"></A>
<A NAME="IDX135"></A>
<A NAME="IDX136"></A>


<P>
The function <CODE>fftwnd_create_plan</CODE> creates a plan, which is a data
structure containing all the information that <CODE>fftwnd</CODE> 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
<CODE>fftw2d_create_plan</CODE> and <CODE>fftw3d_create_plan</CODE> are optional,
alternative interfaces to <CODE>fftwnd_create_plan</CODE> for two and three
dimensions, respectively.


<P>
<CODE>fftwnd_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> 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 <CODE>rank</CODE> &#60;
0).


<P>
The <CODE>create_plan_specific</CODE> variants take as additional arguments
specific input/output arrays and their strides.  For the last four
arguments, you should pass the arrays and strides that you will
eventually be passing to <CODE>fftwnd</CODE>.  The resulting plans will be
optimized for those arrays and strides, although they may be used on
other arrays as well.  Note: the contents of the in and out arrays are
<EM>destroyed</EM> by the specific planner (the initial contents are
ignored, so the arrays need not have been initialized).
See Section <A HREF="fftw_3.html#SEC20">Discussion on Specific Plans</A>, for a discussion on specific plans.



<H4>Arguments</H4>

<UL>
<LI>

<CODE>rank</CODE> is the dimensionality of the arrays to be transformed.  It
can be any non-negative integer.

<LI>

<CODE>n</CODE> is a pointer to an array of <CODE>rank</CODE> 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
<A NAME="IDX137"></A>
row-major arrays--i.e. <CODE>n[0]</CODE> is the size of the dimension whose
indices vary most slowly, and so on. (See Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>, for more information on row-major storage.)
See Section <A HREF="fftw_3.html#SEC19">Plan Creation for One-dimensional Transforms</A>,
for more information regarding optimal array sizes.

<LI>

<CODE>nx</CODE> and <CODE>ny</CODE> in <CODE>fftw2d_create_plan</CODE> are positive
integers specifying the dimensions of the rank 2 array to be
transformed. i.e. they specify that the transform will operate on
<CODE>nx x ny</CODE> arrays in row-major order, where <CODE>nx</CODE> is the number
of rows and <CODE>ny</CODE> is the number of columns.

<LI>

<CODE>nx</CODE>, <CODE>ny</CODE> and <CODE>nz</CODE> in <CODE>fftw3d_create_plan</CODE> are
positive integers specifying the dimensions of the rank 3 array to be
transformed. i.e. they specify that the transform will operate on
<CODE>nx x ny x nz</CODE> arrays in row-major order.

<LI>

<CODE>dir</CODE> is the sign of the exponent in the formula that defines the
Fourier transform.  It can be -1 or +1.  The aliases
<CODE>FFTW_FORWARD</CODE> and <CODE>FFTW_BACKWARD</CODE> are provided, where
<CODE>FFTW_FORWARD</CODE> stands for -1.

<LI>

<A NAME="IDX138"></A>
<CODE>flags</CODE> is a boolean OR (<SAMP>`|'</SAMP>) of zero or more of the following:

<UL>
<LI>

<CODE>FFTW_MEASURE</CODE>: this flag tells FFTW to find the optimal plan by
actually <EM>computing</EM> several FFTs and measuring their execution
time.

<LI>

<CODE>FFTW_ESTIMATE</CODE>: do not run any FFT and provide a "reasonable"
plan (for a RISC processor with many registers).  If neither
<CODE>FFTW_ESTIMATE</CODE> nor <CODE>FFTW_MEASURE</CODE> is provided, the default is
<CODE>FFTW_ESTIMATE</CODE>.

<LI>

<CODE>FFTW_OUT_OF_PLACE</CODE>: produce a plan assuming that the input
  and output arrays will be distinct (this is the default).

<LI>

<CODE>FFTW_IN_PLACE</CODE>: produce a plan assuming that you want to perform
the transform in-place.  (Unlike the one-dimensional transform, this
"really" <A NAME="DOCF3" HREF="fftw_foot.html#FOOT3">(3)</A> performs the
transform in-place.) Note that, if you want to perform in-place
transforms, you <EM>must</EM> use a plan created with this option.

The default mode of operation is <CODE>FFTW_OUT_OF_PLACE</CODE>.

<LI>

<A NAME="IDX139"></A>
<CODE>FFTW_USE_WISDOM</CODE>: use any <CODE>wisdom</CODE> that is available to help
in the creation of the plan. (See Section <A HREF="fftw_2.html#SEC13">Words of Wisdom</A>.)  This can greatly
speed the creation of plans, especially with the <CODE>FFTW_MEASURE</CODE>
option. <CODE>FFTW_ESTIMATE</CODE> plans can also take advantage of
<CODE>wisdom</CODE> to produce a more optimal plan (based on past
measurements) than the estimation heuristic would normally
generate. When the <CODE>FFTW_MEASURE</CODE> option is used, new <CODE>wisdom</CODE>
will also be generated if the current transform size is not completely
understood by existing <CODE>wisdom</CODE>. Note that the same <CODE>wisdom</CODE>
is shared between one-dimensional and multi-dimensional transforms.

</UL>

<LI>

<CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for the
<CODE>_create_plan_specific</CODE> variants): see corresponding arguments in
the description of <CODE>fftwnd</CODE>.  (See Section <A HREF="fftw_3.html#SEC26">Computing the Multi-dimensional Transform</A>.)

</UL>



<H3><A NAME="SEC26">Computing the Multi-dimensional Transform</A></H3>


<PRE>
#include &#60;fftw.h&#62;

void fftwnd(fftwnd_plan plan, int howmany,
            fftw_complex *in, int istride, int idist,
            fftw_complex *out, int ostride, int odist);

void fftwnd_one(fftwnd_plan p, fftw_complex *in, 
                fftw_complex *out);
</PRE>

<P>
<A NAME="IDX140"></A>
<A NAME="IDX141"></A>


<P>
The function <CODE>fftwnd</CODE> computes one or more multi-dimensional
Fourier Transforms, using a plan created by <CODE>fftwnd_create_plan</CODE>
(see Section <A HREF="fftw_3.html#SEC25">Plan Creation for Multi-dimensional Transforms</A>). (Note that the plan determines the rank and dimensions of
the array to be transformed.)  The function <CODE>fftwnd_one</CODE> provides a
simplified interface for the common case of single input array of stride
1.
<A NAME="IDX142"></A>



<H4>Arguments</H4>

<UL>
<LI>

<CODE>plan</CODE> is the plan created by <CODE>fftwnd_create_plan</CODE>.
(see Section <A HREF="fftw_3.html#SEC25">Plan Creation for Multi-dimensional Transforms</A>). In the case of two and three-dimensional transforms, it
could also have been created by <CODE>fftw2d_create_plan</CODE> or