/usr/share/doc/libfftw3-doc/html/Introduction.html

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- This manual is for FFTW
(version 3.3.3, 25 November 2012).

Copyright (C) 2003 Matteo Frigo.

Copyright (C) 2003 Massachusetts Institute of Technology.

Permission is granted to make and distribute verbatim copies of this
manual provided the copyright notice and this permission notice are
preserved on all copies.

Permission is granted to copy and distribute modified versions of this
manual under the conditions for verbatim copying, provided that the
entire resulting derived work is distributed under the terms of a
permission notice identical to this one.

Permission is granted to copy and distribute translations of this manual
into another language, under the above conditions for modified versions,
except that this permission notice may be stated in a translation
approved by the Free Software Foundation. -->
<!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
<head>
<title>FFTW 3.3.3: Introduction</title>

<meta name="description" content="FFTW 3.3.3: Introduction">
<meta name="keywords" content="FFTW 3.3.3: Introduction">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="index.html#Top" rel="up" title="Top">
<link href="Tutorial.html#Tutorial" rel="next" title="Tutorial">
<link href="index.html#Top" rel="prev" title="Top">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Introduction"></a>
<div class="header">
<p>
Next: <a href="Tutorial.html#Tutorial" accesskey="n" rel="next">Tutorial</a>, Previous: <a href="index.html#Top" accesskey="p" rel="prev">Top</a>, Up: <a href="index.html#Top" accesskey="u" rel="up">Top</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Introduction-1"></a>
<h2 class="chapter">1 Introduction</h2>
<p>This manual documents version 3.3.3 of FFTW, the
<em>Fastest Fourier Transform in the West</em>.  FFTW is a comprehensive
collection of fast C routines for computing the discrete Fourier
transform (DFT) and various special cases thereof.
<a name="index-discrete-Fourier-transform"></a>
<a name="index-DFT"></a>
</p><ul>
<li> FFTW computes the DFT of complex data, real data, even-
  or odd-symmetric real data (these symmetric transforms are usually
  known as the discrete cosine or sine transform, respectively), and the
  discrete Hartley transform (DHT) of real data.

</li><li> The input data can have arbitrary length.  
       FFTW employs <i>O</i>(<i>n</i>&nbsp;log&nbsp;<i>n</i>)       prime numbers.

</li><li> FFTW supports arbitrary multi-dimensional data.

</li><li> FFTW supports the SSE, SSE2, AVX, Altivec, and MIPS PS instruction
       sets.

</li><li> FFTW includes parallel (multi-threaded) transforms
       for shared-memory systems.
</li><li> Starting with version 3.3, FFTW includes distributed-memory parallel
       transforms using MPI.
</li></ul>

<p>We assume herein that you are familiar with the properties and uses of
the DFT that are relevant to your application.  Otherwise, see
e.g. <cite>The Fast Fourier Transform and Its Applications</cite> by E. O. Brigham
(Prentice-Hall, Englewood Cliffs, NJ, 1988).
<a href="http://www.fftw.org">Our web page</a> also has links to FFT-related
information online.
<a name="index-FFTW"></a>
</p>

<p>In order to use FFTW effectively, you need to learn one basic concept
of FFTW&rsquo;s internal structure: FFTW does not use a fixed algorithm for
computing the transform, but instead it adapts the DFT algorithm to
details of the underlying hardware in order to maximize performance.
Hence, the computation of the transform is split into two phases.
First, FFTW&rsquo;s <em>planner</em> &ldquo;learns&rdquo; the fastest way to compute the
transform on your machine.  The planner
<a name="index-planner"></a>
produces a data structure called a <em>plan</em> that contains this
<a name="index-plan"></a>
information.  Subsequently, the plan is <em>executed</em>
<a name="index-execute"></a>
to transform the array of input data as dictated by the plan.  The
plan can be reused as many times as needed.  In typical
high-performance applications, many transforms of the same size are
computed and, consequently, a relatively expensive initialization of
this sort is acceptable.  On the other hand, if you need a single
transform of a given size, the one-time cost of the planner becomes
significant.  For this case, FFTW provides fast planners based on
heuristics or on previously computed plans.
</p>
<p>FFTW supports transforms of data with arbitrary length, rank,
multiplicity, and a general memory layout.  In simple cases, however,
this generality may be unnecessary and confusing.  Consequently, we
organized the interface to FFTW into three levels of increasing
generality.
</p><ul>
<li> The <em>basic interface</em> computes a single 
      transform of contiguous data.
</li><li> The <em>advanced interface</em> computes transforms 
      of multiple or strided arrays.
</li><li> The <em>guru interface</em> supports the most general data 
      layouts, multiplicities, and strides.
</li></ul>
<p>We expect that most users will be best served by the basic interface,
whereas the guru interface requires careful attention to the
documentation to avoid problems.
<a name="index-basic-interface"></a>
<a name="index-advanced-interface"></a>
<a name="index-guru-interface"></a>
</p>

<p>Besides the automatic performance adaptation performed by the planner,
it is also possible for advanced users to customize FFTW manually.  For
example, if code space is a concern, we provide a tool that links only
the subset of FFTW needed by your application.  Conversely, you may need
to extend FFTW because the standard distribution is not sufficient for
your needs.  For example, the standard FFTW distribution works most
efficiently for arrays whose size can be factored into small primes
(<em>2</em>, <em>3</em>, <em>5</em>, and <em>7</em>), and otherwise it uses a
slower general-purpose routine.  If you need efficient transforms of
other sizes, you can use FFTW&rsquo;s code generator, which produces fast C
programs (&ldquo;codelets&rdquo;) for any particular array size you may care
about.
<a name="index-code-generator"></a>
<a name="index-codelet"></a>
For example, if you need transforms of size
513&nbsp;=&nbsp;19*3<sup>3</sup>,you can customize FFTW to support the factor <em>19</em> efficiently.
</p>
<p>For more information regarding FFTW, see the paper, &ldquo;The Design and
Implementation of FFTW3,&rdquo; by M. Frigo and S. G. Johnson, which was an
invited paper in <cite>Proc. IEEE</cite> <b>93</b> (2), p. 216 (2005).  The
code generator is described in the paper &ldquo;A fast Fourier transform
compiler&rdquo;,
<a name="index-compiler"></a>
by M. Frigo, in the <cite>Proceedings of the 1999 ACM SIGPLAN Conference
on Programming Language Design and Implementation (PLDI), Atlanta,
Georgia, May 1999</cite>.  These papers, along with the latest version of
FFTW, the FAQ, benchmarks, and other links, are available at
<a href="http://www.fftw.org">the FFTW home page</a>.  
</p>
<p>The current version of FFTW incorporates many good ideas from the past
thirty years of FFT literature.  In one way or another, FFTW uses the
Cooley-Tukey algorithm, the prime factor algorithm, Rader&rsquo;s algorithm
for prime sizes, and a split-radix algorithm (with a
&ldquo;conjugate-pair&rdquo; variation pointed out to us by Dan Bernstein).
FFTW&rsquo;s code generator also produces new algorithms that we do not
completely understand.
<a name="index-algorithm"></a>
The reader is referred to the cited papers for the appropriate
references.
</p>
<p>The rest of this manual is organized as follows.  We first discuss the
sequential (single-processor) implementation.  We start by describing
the basic interface/features of FFTW in <a href="Tutorial.html#Tutorial">Tutorial</a>.  
Next, <a href="Other-Important-Topics.html#Other-Important-Topics">Other Important Topics</a> discusses data alignment
(see <a href="SIMD-alignment-and-fftw_005fmalloc.html#SIMD-alignment-and-fftw_005fmalloc">SIMD alignment and fftw_malloc</a>),
the storage scheme of multi-dimensional arrays
(see <a href="Multi_002ddimensional-Array-Format.html#Multi_002ddimensional-Array-Format">Multi-dimensional Array Format</a>), and FFTW&rsquo;s mechanism for
storing plans on disk (see <a href="Words-of-Wisdom_002dSaving-Plans.html#Words-of-Wisdom_002dSaving-Plans">Words of Wisdom-Saving Plans</a>).  Next,
<a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a> provides comprehensive documentation of all
FFTW&rsquo;s features.  Parallel transforms are discussed in their own
chapters: <a href="Multi_002dthreaded-FFTW.html#Multi_002dthreaded-FFTW">Multi-threaded FFTW</a> and <a href="Distributed_002dmemory-FFTW-with-MPI.html#Distributed_002dmemory-FFTW-with-MPI">Distributed-memory FFTW with MPI</a>.  Fortran programmers can also use FFTW, as described in
<a href="Calling-FFTW-from-Legacy-Fortran.html#Calling-FFTW-from-Legacy-Fortran">Calling FFTW from Legacy Fortran</a> and <a href="Calling-FFTW-from-Modern-Fortran.html#Calling-FFTW-from-Modern-Fortran">Calling FFTW from Modern Fortran</a>.  <a href="Installation-and-Customization.html#Installation-and-Customization">Installation and Customization</a> explains how to
install FFTW in your computer system and how to adapt FFTW to your
needs.  License and copyright information is given in <a href="License-and-Copyright.html#License-and-Copyright">License and Copyright</a>.  Finally, we thank all the people who helped us in
<a href="Acknowledgments.html#Acknowledgments">Acknowledgments</a>.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Tutorial.html#Tutorial" accesskey="n" rel="next">Tutorial</a>, Previous: <a href="index.html#Top" accesskey="p" rel="prev">Top</a>, Up: <a href="index.html#Top" accesskey="u" rel="up">Top</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
</div>



</body>
</html>
libfftw3-doc 3.3.3-7ubuntu3 / usr / share / doc / libfftw3-doc / html / Introduction.html
