fftw.texi

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

@subsection Importing and Exporting Wisdom
@cindex wisdom, import and export

@example
void fftw_export_wisdom_to_file(FILE *output_file);
fftw_status fftw_import_wisdom_from_file(FILE *input_file);
@end example
@findex fftw_export_wisdom_to_file
@findex fftw_import_wisdom_from_file

@code{fftw_export_wisdom_to_file} writes the @code{wisdom} to
@code{output_file}, which must be a file open for
writing. @code{fftw_import_wisdom_from_file} reads the @code{wisdom}
from @code{input_file}, which must be a file open for reading, and
returns @code{FFTW_SUCCESS} if successful and @code{FFTW_FAILURE}
otherwise. In both cases, the file is left open and must be closed by
the caller.  It is perfectly fine if other data lie before or after the
@code{wisdom} in the file, as long as the file is positioned at the
beginning of the @code{wisdom} data before import.

@example
char *fftw_export_wisdom_to_string(void);
fftw_status fftw_import_wisdom_from_string(const char *input_string)
@end example
@findex fftw_export_wisdom_to_string
@findex fftw_import_wisdom_from_string

@code{fftw_export_wisdom_to_string} allocates a string, exports the
@code{wisdom} to it in @code{NULL}-terminated format, and returns a
pointer to the string.  If there is an error in allocating or writing
the data, it returns @code{NULL}.  The caller is responsible for
deallocating the string (with @code{fftw_free}) when she is done with
it. @code{fftw_import_wisdom_from_string} imports the @code{wisdom} from
@code{input_string}, returning @code{FFTW_SUCCESS} if successful and
@code{FFTW_FAILURE} otherwise.

Exporting @code{wisdom} does not affect the store of @code{wisdom}. Imported
@code{wisdom} supplements the current store rather than replacing it
(except when there is conflicting @code{wisdom}, in which case the older
@code{wisdom} is discarded). The format of the exported @code{wisdom} is
``nerd-readable'' LISP-like ASCII text; we will not document it here
except to note that it is insensitive to white space (interested users
can contact us for more details).
@cindex LISP
@cindex nerd-readable text

@xref{FFTW Reference}, for more information, and for a description of
how you can implement @code{wisdom} import/export for other media
besides files and strings.

The following is a brief example in which the @code{wisdom} is read from
a file, a plan is created (possibly generating more @code{wisdom}), and
then the @code{wisdom} is exported to a string and printed to
@code{stdout}.

@example
@{
     fftw_plan plan;
     char *wisdom_string;
     FILE *input_file;

     /* open file to read wisdom from */
     input_file = fopen("sample.wisdom", "r");
     if (FFTW_FAILURE == fftw_import_wisdom_from_file(input_file))
          printf("Error reading wisdom!\n");
     fclose(input_file); /* be sure to close the file! */

     /* create a plan for N=64, possibly creating and/or using wisdom */
     plan = fftw_create_plan(64,FFTW_FORWARD,
                             FFTW_MEASURE | FFTW_USE_WISDOM);

     /* ... do some computations with the plan ... */

     /* always destroy plans when you are done */
     fftw_destroy_plan(plan);

     /* write the wisdom to a string */
     wisdom_string = fftw_export_wisdom_to_string();
     if (wisdom_string != NULL) @{
          printf("Accumulated wisdom: %s\n",wisdom_string);

          /* Just for fun, destroy and restore the wisdom */
          fftw_forget_wisdom(); /* all gone! */
          fftw_import_wisdom_from_string(wisdom_string);
          /* wisdom is back! */

          fftw_free(wisdom_string); /* deallocate it since we're done */
     @}
@}
@end example

@c ************************************************************
@node FFTW Reference, Parallel FFTW, Tutorial, Top
@chapter FFTW Reference

This chapter provides a complete reference for all sequential (i.e.,
one-processor) FFTW functions.  We first define the data types upon
which FFTW operates, that is, real, complex, and ``halfcomplex'' numbers
(@pxref{Data Types}).  Then, in four sections, we explain the FFTW
program interface for complex one-dimensional transforms
(@pxref{One-dimensional Transforms Reference}), complex
multi-dimensional transforms (@pxref{Multi-dimensional Transforms
Reference}), and real one-dimensional transforms (@pxref{Real
One-dimensional Transforms Reference}), real multi-dimensional
transforms (@pxref{Real Multi-dimensional Transforms Reference}).
@ref{Wisdom Reference} describes the @code{wisdom} mechanism for
exporting and importing plans.  Finally, @ref{Memory Allocator
Reference} describes how to change FFTW's default memory allocator.
For parallel transforms, @xref{Parallel FFTW}.

@menu
* Data Types::                  real, complex, and halfcomplex numbers
* One-dimensional Transforms Reference::  
* Multi-dimensional Transforms Reference::  
* Real One-dimensional Transforms Reference::  
* Real Multi-dimensional Transforms Reference::  
* Wisdom Reference::            
* Memory Allocator Reference::  
* Thread safety::               
@end menu

@c -------------------------------------------------------
@node Data Types, One-dimensional Transforms Reference, FFTW Reference, FFTW Reference
@section Data Types
@cindex real number
@cindex complex number
@cindex halfcomplex array

The routines in the FFTW package use three main kinds of data types.
@dfn{Real} and @dfn{complex} numbers should be already known to the
reader.  We also use the term @dfn{halfcomplex} to describe complex
arrays in a special packed format used by the one-dimensional real
transforms (taking advantage of the @dfn{hermitian} symmetry that arises
in those cases).

By including @code{<fftw.h>} or @code{<rfftw.h>}, you will have access
to the following definitions:

@example
typedef double fftw_real;

typedef struct @{
     fftw_real re, im;
@} fftw_complex;

#define c_re(c)  ((c).re)
#define c_im(c)  ((c).im)
@end example
@tindex fftw_real
@tindex fftw_complex

All FFTW operations are performed on the @code{fftw_real} and
@code{fftw_complex} data types.  For @code{fftw_complex} numbers, the
two macros @code{c_re} and @code{c_im} retrieve, respectively, the real
and imaginary parts of the number.

A @dfn{real array} is an array of real numbers.  A @dfn{complex array}
is an array of complex numbers.  A one-dimensional array @math{X} of
@math{n} complex numbers is @dfn{hermitian} if the following property
holds:
@tex
for all $0 \leq i < n$, we have $X_i = X^{*}_{n-i}$, where
$x^*$ denotes the complex conjugate of $x$.
@end tex
@ifinfo
for all @math{0 <= i < n}, we have @math{X[i] = conj(X[n-i])}.
@end ifinfo
@ifhtml
for all 0 &lt;= i &lt; n, we have X<sub>i</sub> = conj(X<sub>n-i</sub>)}.
@end ifhtml
Hermitian arrays are relevant to FFTW because the Fourier transform of a
real array is hermitian.

Because of its symmetry, a hermitian array can be stored in half the
space of a complex array of the same size.  FFTW's one-dimensional real
transforms store hermitian arrays as @dfn{halfcomplex} arrays.  A
halfcomplex array of size @math{n} is
@cindex hermitian array
a one-dimensional array of @math{n} @code{fftw_real} numbers.  A
hermitian array @math{X} in stored into a halfcomplex array @math{Y} as
follows.
@tex
For all integers $i$ such that $0 \leq i \leq n / 2$, we have $Y_i :=
\hbox{Re}(X_i)$.  For all integers $i$ such that $0 < i < n / 2$,
we have $Y_{n - i} := \hbox{Im}(X_i)$.
@end tex
@ifinfo
For all integers @math{i} such that @math{0 <= i <= n / 2}, we have
@math{Y[i] = Re(X[i])}.  For all integers @math{i} such that @math{0 <
i < n / 2}, we have @math{Y[n-i] = Im(X[i])}.
@end ifinfo
@ifhtml
For all integers i such that 0 &lt;= i &lt;= n / 2, we have
Y<sub>i</sub> = Re(X<sub>i</sub>).  For all integers i such that 0
&lt; i &lt; n / 2, we have Y<sub>n-i</sub> = Im(X<sub>i</sub>).
@end ifhtml

We now illustrate halfcomplex storage for @math{n = 4} and @math{n = 5},
since the scheme depends on the parity of @math{n}.  Let @math{n = 4}.
In this case, we have
@tex
$Y_0 := \hbox{Re}(X_0)$, $Y_1 := \hbox{Re}(X_1)$,
$Y_2 := \hbox{Re}(X_2)$, and $Y_3 := \hbox{Im}(X_1)$.
@end tex
@ifinfo
@math{Y[0] = Re(X[0])}, @math{Y[1] = Re(X[1])},
@math{Y[2] = Re(X[2])}, and  @math{Y[3] = Im(X[1])}.
@end ifinfo
@ifhtml
Y<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>),
Y<sub>2</sub> = Re(X<sub>2</sub>), and  Y<sub>3</sub> = Im(X<sub>1</sub>).
@end ifhtml
Let now @math{n = 5}.  In this case, we have
@tex
$Y_0 := \hbox{Re}(X_0)$, $Y_1 := \hbox{Re}(X_1)$,
$Y_2 := \hbox{Re}(X_2)$, $Y_3 := \hbox{Im}(X_2)$, and 
$Y_4 := \hbox{Im}(X_1)$.
@end tex
@ifinfo
@math{Y[0] = Re(X[0])}, @math{Y[1] = Re(X[1])},
@math{Y[2] = Re(X[2])}, @math{Y[3] = Im(X[2])}, and
@math{Y[4] = Im(X[1])}.
@end ifinfo
@ifhtml
Y<sub>0</sub> = Re(X<sub>0</sub>), Y<sub>1</sub> = Re(X<sub>1</sub>),
Y<sub>2</sub> = Re(X<sub>2</sub>), Y<sub>3</sub> = Im(X<sub>2</sub>),
and Y<sub>4</sub> = Im(X<sub>1</sub>).
@end ifhtml

@cindex floating-point precision
By default, the type @code{fftw_real} equals the C type @code{double}.
To work in single precision rather than double precision, @code{#define}
the symbol @code{FFTW_ENABLE_FLOAT} in @code{fftw.h} and then recompile
the library.  On Unix systems, you can instead use @code{configure
--enable-float} at installation time (@pxref{Installation and
Customization}).
@fpindex configure
@ctindex FFTW_ENABLE_FLOAT

In version 1 of FFTW, the data types were called @code{FFTW_REAL} and
@code{FFTW_COMPLEX}.  We changed the capitalization for consistency with
the rest of FFTW's conventions.  The old names are still supported, but
their use is deprecated.
@tindex FFTW_REAL
@tindex FFTW_COMPLEX

@c -------------------------------------------------------
@node One-dimensional Transforms Reference, Multi-dimensional Transforms Reference, Data Types, FFTW Reference
@section One-dimensional Transforms Reference

The one-dimensional complex routines are generally prefixed with
@code{fftw_}.  Programs using FFTW should be linked with @code{-lfftw
-lm} on Unix systems, or with the FFTW and standard math libraries in
general.

@menu
* fftw_create_plan::            Plan Creation
* Discussion on Specific Plans::  
* fftw::                        Plan Execution
* fftw_destroy_plan::           Plan Destruction
* What FFTW Really Computes::   Definition of the DFT.
@end menu

@node    fftw_create_plan, Discussion on Specific Plans, One-dimensional Transforms Reference, One-dimensional Transforms Reference
@subsection Plan Creation for One-dimensional Transforms

@example
#include <fftw.h>

fftw_plan fftw_create_plan(int n, fftw_direction dir,
                           int flags);

fftw_plan fftw_create_plan_specific(int n, fftw_direction dir,
                                    int flags,
                                    fftw_complex *in, int istride,
                                    fftw_complex *out, int ostride);
@end example
@tindex fftw_plan
@tindex fftw_direction
@findex fftw_create_plan
@findex fftw_create_plan_specific

The function @code{fftw_create_plan} creates a plan, which is
a data structure containing all the information that @code{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).

@code{fftw_create_plan} returns a valid plan, or @code{NULL}
if, for some reason, the plan can't be created.  In the
default installation, this cannot happen, but it is possible
to configure FFTW in such a way that some input sizes are
forbidden, and FFTW cannot create a plan.

The @code{fftw_create_plan_specific} 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{fftw}.  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
@emph{destroyed} by the specific planner (the initial contents are
ignored, so the arrays need not have been initialized).

@subsubheading Arguments
@itemize @bullet
@item
@code{n} is the size of the transform.  It can be
 any positive integer.
 
@itemize @minus
@item
FFTW is best at handling sizes of the form
@ifinfo
@math{2^a 3^b 5^c 7^d 11^e 13^f},
@end ifinfo
@tex
$2^a 3^b 5^c 7^d 11^e 13^f$,
@end tex
@ifhtml
2<SUP>a</SUP> 3<SUP>b</SUP> 5<SUP>c</SUP> 7<SUP>d</SUP>
        11<SUP>e</SUP> 13<SUP>f</SUP>,
@end ifhtml
where @math{e+f} is either @math{0} or
@math{1}, and the other exponents are arbitrary.  Other sizes are
computed by means of a slow, general-purpose routine (which nevertheless
retains 
@tex
$O(n \lo