fftw_3.html

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

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


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

void rfftw_destroy_plan(rfftw_plan plan);
</PRE>

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


<P>
The function <CODE>rfftw_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="SEC33">What RFFTW Really Computes</A></H3>
<P>
<A NAME="IDX159"></A>
In this section, we define precisely what RFFTW computes. 


<P>
The real to complex (<CODE>FFTW_REAL_TO_COMPLEX</CODE>) transform of a real
array X of size n computes an hermitian array Y,
where
<center><IMG SRC="equation-1.gif" ALIGN="top"></center>
(That Y is a hermitian array is not intended to be obvious,
although the proof is easy.)  The hermitian array Y is stored in
halfcomplex order (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>).  Currently, RFFTW provides no
way to compute a real to complex transform with a positive sign in the
exponent.


<P>
The complex to real (<CODE>FFTW_COMPLEX_TO_REAL</CODE>) transform of a hermitian
array X of size n computes a real array Y, where
<center><IMG SRC="equation-2.gif" ALIGN="top"></center>
(That Y is a real array is not intended to be obvious, although
the proof is easy.)  The hermitian input array X is stored in
halfcomplex order (see Section <A HREF="fftw_3.html#SEC17">Data Types</A>).  Currently, RFFTW provides no
way to compute a complex to real transform with a negative sign in the
exponent.


<P>
<A NAME="IDX160"></A>
Like FFTW, RFFTW computes an unnormalized transform.  In other words,
applying the real to complex (forward) and then the complex to real
(backward) transform will multiply the input by n.




<H2><A NAME="SEC34">Real Multi-dimensional Transforms Reference</A></H2>
<P>
<A NAME="IDX161"></A>
<A NAME="IDX162"></A>


<P>
The multi-dimensional real routines are generally prefixed with
<CODE>rfftwnd_</CODE>.  Programs using RFFTWND should be linked with
<CODE>-lrfftw -lfftw -lm</CODE> on Unix systems, or with the FFTW, RFFTW, and
standard math libraries in general.
<A NAME="IDX163"></A>




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


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

rfftwnd_plan rfftwnd_create_plan(int rank, const int *n,
                                 fftw_direction dir, int flags);

rfftwnd_plan rfftw2d_create_plan(int nx, int ny,
                                 fftw_direction dir, int flags);

rfftwnd_plan rfftw3d_create_plan(int nx, int ny, int nz,
                                 fftw_direction dir, int flags);
</PRE>

<P>
<A NAME="IDX164"></A>
<A NAME="IDX165"></A>
<A NAME="IDX166"></A>
<A NAME="IDX167"></A>
<A NAME="IDX168"></A>


<P>
The function <CODE>rfftwnd_create_plan</CODE> creates a plan, which is a data
structure containing all the information that <CODE>rfftwnd</CODE> needs in
order to compute a multi-dimensional 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).  The functions
<CODE>rfftw2d_create_plan</CODE> and <CODE>rfftw3d_create_plan</CODE> are optional,
alternative interfaces to <CODE>rfftwnd_create_plan</CODE> for two and three
dimensions, respectively.


<P>
<CODE>rfftwnd_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 the
arguments are invalid in some way (e.g. if <CODE>rank</CODE> &#60; 0).



<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.  Note that these
are always the dimensions of the <EM>real</EM> arrays; the complex arrays
have different dimensions (see Section <A HREF="fftw_3.html#SEC37">Array Dimensions for Real Multi-dimensional Transforms</A>).  These sizes, which must be positive
integers, correspond to the dimensions of 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.)

<UL>
<LI>

See Section <A HREF="fftw_3.html#SEC30">Plan Creation for Real One-dimensional Transforms</A>,
for more information regarding optimal array sizes.
</UL>

<LI>

<CODE>nx</CODE> and <CODE>ny</CODE> in <CODE>rfftw2d_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>rfftw3d_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 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.

<LI>

<A NAME="IDX169"></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>

<A NAME="IDX170"></A>
<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" 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 use of this option has important implications for the
size of the input/output array (see Section <A HREF="fftw_3.html#SEC36">Computing the Real Multi-dimensional Transform</A>).

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

<LI>

<A NAME="IDX171"></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>

</UL>



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


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

void rfftwnd_real_to_complex(rfftwnd_plan plan, int howmany,
                             fftw_real *in, int istride, int idist,
                             fftw_complex *out, int ostride, int odist);
void rfftwnd_complex_to_real(rfftwnd_plan plan, int howmany,
                             fftw_complex *in, int istride, int idist,
                             fftw_real *out, int ostride, int odist);

void rfftwnd_one_real_to_complex(rfftwnd_plan p, fftw_real *in,
                                 fftw_complex *out);
void rfftwnd_one_complex_to_real(rfftwnd_plan p, fftw_complex *in,
                                 fftw_real *out);
</PRE>

<P>
<A NAME="IDX172"></A>
<A NAME="IDX173"></A>
<A NAME="IDX174"></A>
<A NAME="IDX175"></A>


<P>
These functions compute the real multi-dimensional Fourier Transform,
using a plan created by <CODE>rfftwnd_create_plan</CODE>
(see Section <A HREF="fftw_3.html#SEC35">Plan Creation for Real Multi-dimensional Transforms</A>). (Note that the plan determines the rank and dimensions of
the array to be transformed.)  The <SAMP>`<CODE>rfftwnd_one_</CODE>'</SAMP> functions
provide a simplified interface for the common case of single input array
of stride 1.  Unlike other transform routines in FFTW, we here use
separate functions for the two directions of the transform in order to
correctly express the datatypes of the parameters.


<P>
<EM>Important:</EM> When invoked for an out-of-place,
<CODE>FFTW_COMPLEX_TO_REAL</CODE> transform with <CODE>rank &#62; 1</CODE>, 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 or for
<CODE>FFTW_COMPLEX_TO_REAL</CODE> with <CODE>rank == 1</CODE>.



<H4>Arguments</H4>

<UL>
<LI>

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

<CODE>FFTW_REAL_TO_COMPLEX</CODE> plans must be used with the
<SAMP>`<CODE>real_to_complex</CODE>'</SAMP> functions, and <CODE>FFTW_COMPLEX_TO_REAL</CODE>
plans must be used with the <SAMP>`<CODE>complex_to_real</CODE>'</SAMP> functions.  It
is an error to mismatch the plan direction and the transform function.

<LI>

<CODE>howmany</CODE> is the number of transforms to be computed.

<LI>

<A NAME="IDX176"></A>
<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 is stored in
row-major format (see Section <A HREF="fftw_2.html#SEC7">Multi-dimensional Array Format</A>), and is 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.

The dimensions of the arrays are different for real and complex data,
and are discussed in more detail below (see Section <A HREF="fftw_3.html#SEC37">Array Dimensions for Real Multi-dimensional Transforms</A>).


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

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.  The
meaning of the <CODE>stride</CODE> and <CODE>dist</CODE> parameters in this case is
subtle and is discussed below (see Section <A HREF="fftw_3.html#SEC38">Strides in In-place RFFTWND</A>).
</UL>

<LI>

<CODE>out</CODE>, <CODE>ostride</CODE> and <CODE>odist</CODE> describe the output
array(s).  The format is the same as that for the input array.  See
below for a discussion of the dimensions of the output array for real
and complex data.


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

<PRE>
rfftwnd_one_...(plan, in, out)
</PRE>

<P>
is equivalent to

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



<H3><A NAME="SEC37">Array Dimensions for Real Multi-dimensional Transforms</A></H3>

<P>
<A NAME="IDX177"></A>
The output of a multi-dimensional transform of real data contains
symmetries that, in principle, make half of the outputs redundant
(see Section <A HREF="fftw_3.html#SEC40">What RFFTWND Really Computes</A>).  In practice, it is not
possible to entirely realize these savings in an efficient and
understandable format.  Instead, the output of the rfftwnd transforms is
<EM>slightly</EM> over half of the output of the corresponding complex
transform.  We do not "pack" the data in any way, but store it as an
ordinary array of <CODE>fftw_complex</CODE> values.  In fact, this data is
simply a subsection of what would be the array in the corresponding
complex transform.