fftw_3.html

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

<CODE>fftw3d_create_plan</CODE>, respectively.

<LI>

<CODE>howmany</CODE> is the number of multi-dimensional transforms
<CODE>fftwnd</CODE> will compute.

<LI>

<CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s).
There are <CODE>howmany</CODE> multi-dimensional 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
multi-dimensional input array consists of complex numbers (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>), stored in row-major format (see Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</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>. Note that, here, <CODE>i</CODE> refers to
an index into the row-major format for the multi-dimensional array,
rather than an index in any particular dimension.


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

<A NAME="IDX143"></A>
For plans created with the <CODE>FFTW_IN_PLACE</CODE> option, the transform is
computed in-place--the output is returned in the <CODE>in</CODE> array, using
the same strides, etcetera, as were used in the input.
</UL>

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

These parameters are ignored for plans created with the
<CODE>FFTW_IN_PLACE</CODE> option.
</UL>

</UL>

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

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

<P>
is equivalent to

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



<H3><A NAME="SEC27">Destroying a Multi-dimensional Plan</A></H3>


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

void fftwnd_destroy_plan(fftwnd_plan plan);
</PRE>

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


<P>
The function <CODE>fftwnd_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="SEC28">What FFTWND Really Computes</A></H3>
<P>
<A NAME="IDX145"></A>


<P>
The conventions that we follow for the multi-dimensional transform are
analogous to those for the one-dimensional transform. In particular, the
forward transform has a negative sign in the exponent and neither the
forward nor the backward transforms will perform any normalization.
Computing the backward transform of the forward transform will multiply
the array by the product of its dimensions.  The output is in-order, and
the zeroth element of the output is the amplitude of the zero frequency
component.


The Gods forbade using HTML to display mathematical formulas.  Please
see the TeX or Postscript version of this manual for the proper
definition of the n-dimensional Fourier transform that FFTW
uses.  For completeness, we include a bitmap of the TeX output below:
<P><center><IMG SRC="equation-3.gif" ALIGN="top"></center>



<H2><A NAME="SEC29">Real One-dimensional Transforms Reference</A></H2>

<P>
The one-dimensional real routines are generally prefixed with
<CODE>rfftw_</CODE>. <A NAME="DOCF4" HREF="fftw_foot.html#FOOT4">(4)</A>  Programs using RFFTW
should be linked with <CODE>-lrfftw -lfftw -lm</CODE> on Unix systems, or with
the RFFTW, the FFTW, and the standard math libraries in general.
<A NAME="IDX146"></A>
<A NAME="IDX147"></A>
<A NAME="IDX148"></A>




<H3><A NAME="SEC30">Plan Creation for Real One-dimensional Transforms</A></H3>


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

rfftw_plan rfftw_create_plan(int n, fftw_direction dir, int flags);

rfftw_plan rfftw_create_plan_specific(int n, fftw_direction dir,
	    int flags, fftw_real *in, int istride,
	    fftw_real *out, int ostride);
</PRE>

<P>
<A NAME="IDX149"></A>
<A NAME="IDX150"></A>
<A NAME="IDX151"></A>


<P>
The function <CODE>rfftw_create_plan</CODE> creates a plan, which is a data
structure containing all the information that <CODE>rfftw</CODE> needs in
order to compute the 1D real 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).


<P>
<CODE>rfftw_create_plan</CODE> returns a valid plan, or <CODE>NULL</CODE> if, for
some reason, the plan can't be created.  In the default installation,
this cannot happen, but it is possible to configure RFFTW in such a way
that some input sizes are forbidden, and RFFTW cannot create a plan.


<P>
The <CODE>rfftw_create_plan_specific</CODE> variant takes 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>rfftw</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>n</CODE> is the size of the transform.  It can be
 any positive integer.
 

<UL>
<LI>

RFFTW is best at handling sizes of the form
2<SUP>a</SUP> 3<SUP>b</SUP> 5<SUP>c</SUP> 7<SUP>d</SUP>
        11<SUP>e</SUP> 13<SUP>f</SUP>,
where e+f is either 0 or
1, and the other exponents are arbitrary.  Other sizes are
computed by means of a slow, general-purpose routine (reducing to
O(n<sup>2</sup>)
performance for prime sizes).  (It is possible to customize RFFTW for
different array sizes.  See Section <A HREF="fftw_6.html#SEC66">Installation and Customization</A>, for more
information.)  Transforms whose sizes are powers of 2 are
especially fast.  If you have large prime factors, it may be faster to
switch over to the complex FFTW routines, which have
O(n lg n)
performance even for prime sizes (we don't know of a similar algorithm
specialized for real data, unfortunately).

</UL>

<LI>

<CODE>dir</CODE> is the direction of the desired transform, either
<CODE>FFTW_REAL_TO_COMPLEX</CODE> or <CODE>FFTW_COMPLEX_TO_REAL</CODE>,
corresponding to <CODE>FFTW_FORWARD</CODE> or <CODE>FFTW_BACKWARD</CODE>,
respectively.
<A NAME="IDX152"></A>
<A NAME="IDX153"></A>

<LI>

<A NAME="IDX154"></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 RFFTW to find the optimal plan by
actually <EM>computing</EM> several FFTs and measuring their
execution time.  Depending on the installation, this can take some
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 the output
in the input array.  The algorithm used is not necessarily in place:
RFFTW is able to compute true in-place transforms only for small values
of <CODE>n</CODE>.  If RFFTW 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.
<EM>Warning: This option changes the meaning of some parameters of
<CODE>rfftw</CODE></EM> (see Section <A HREF="fftw_3.html#SEC31">Computing the Real One-dimensional Transform</A>).

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

<LI>

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

</UL>

<LI>

<CODE>in</CODE>, <CODE>out</CODE>, <CODE>istride</CODE>, <CODE>ostride</CODE> (only for
<CODE>rfftw_create_plan_specific</CODE>): see corresponding arguments in the
description of <CODE>rfftw</CODE>.  (See Section <A HREF="fftw_3.html#SEC31">Computing the Real One-dimensional Transform</A>.)  In particular, the <CODE>out</CODE> and
<CODE>ostride</CODE> parameters have the same special meaning for
<CODE>FFTW_IN_PLACE</CODE> transforms as they have for <CODE>rfftw</CODE>.

</UL>



<H3><A NAME="SEC31">Computing the Real One-dimensional Transform</A></H3>


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

void rfftw(rfftw_plan plan, int howmany, 
           fftw_real *in, int istride, int idist, 
           fftw_real *out, int ostride, int odist);

void rfftw_one(rfftw_plan plan, fftw_real *in, fftw_real *out);
</PRE>

<P>
<A NAME="IDX155"></A>
<A NAME="IDX156"></A>


<P>
The function <CODE>rfftw</CODE> computes the Real One-dimensional Fourier
Transform, using a plan created by <CODE>rfftw_create_plan</CODE>
(see Section <A HREF="fftw_3.html#SEC30">Plan Creation for Real One-dimensional Transforms</A>).  The function <CODE>rfftw_one</CODE> provides a simplified
interface for the common case of single input array of stride 1.
<A NAME="IDX157"></A>


<P>
<EM>Important:</EM> When invoked for an out-of-place,
<CODE>FFTW_COMPLEX_TO_REAL</CODE> transform, the input array is overwritten
with scratch values by these routines.  The input array is not modified
for <CODE>FFTW_REAL_TO_COMPLEX</CODE> transforms.



<H4>Arguments</H4>

<UL>
<LI>

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

<LI>

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

<LI>

<CODE>in</CODE>, <CODE>istride</CODE> and <CODE>idist</CODE> describe the input array(s).
There are two cases.  If the <CODE>plan</CODE> defines a
<CODE>FFTW_REAL_TO_COMPLEX</CODE> transform, <CODE>in</CODE> is a real array.
Otherwise, for <CODE>FFTW_COMPLEX_TO_REAL</CODE> transforms, <CODE>in</CODE> is a
halfcomplex array <EM>whose contents will be destroyed</EM>.

<LI>

<CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output
array(s), and have the same meaning as the corresponding parameters for
the input array.


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

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>rfftw_one</CODE> transforms a single, contiguous input array
to a contiguous output array.  By definition, the call

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

<P>
is equivalent to

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