214 lines
11 KiB
HTML
214 lines
11 KiB
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.10, 10 December 2020).
|
||
|
|
|
||
|
|
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 6.7, http://www.gnu.org/software/texinfo/ -->
|
||
|
|
<head>
|
||
|
|
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
|
||
|
|
<title>Introduction (FFTW 3.3.10)</title>
|
||
|
|
|
||
|
|
<meta name="description" content="Introduction (FFTW 3.3.10)">
|
||
|
|
<meta name="keywords" content="Introduction (FFTW 3.3.10)">
|
||
|
|
<meta name="resource-type" content="document">
|
||
|
|
<meta name="distribution" content="global">
|
||
|
|
<meta name="Generator" content="makeinfo">
|
||
|
|
<link href="index.html" rel="start" title="Top">
|
||
|
|
<link href="Concept-Index.html" rel="index" title="Concept Index">
|
||
|
|
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
|
||
|
|
<link href="index.html" rel="up" title="Top">
|
||
|
|
<link href="Tutorial.html" rel="next" title="Tutorial">
|
||
|
|
<link href="index.html" rel="prev" title="Top">
|
||
|
|
<style type="text/css">
|
||
|
|
<!--
|
||
|
|
a.summary-letter {text-decoration: none}
|
||
|
|
blockquote.indentedblock {margin-right: 0em}
|
||
|
|
div.display {margin-left: 3.2em}
|
||
|
|
div.example {margin-left: 3.2em}
|
||
|
|
div.lisp {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}
|
||
|
|
span.nolinebreak {white-space: nowrap}
|
||
|
|
span.roman {font-family: initial; font-weight: normal}
|
||
|
|
span.sansserif {font-family: sans-serif; font-weight: normal}
|
||
|
|
ul.no-bullet {list-style: none}
|
||
|
|
-->
|
||
|
|
</style>
|
||
|
|
|
||
|
|
|
||
|
|
</head>
|
||
|
|
|
||
|
|
<body lang="en">
|
||
|
|
<span id="Introduction"></span><div class="header">
|
||
|
|
<p>
|
||
|
|
Next: <a href="Tutorial.html" accesskey="n" rel="next">Tutorial</a>, Previous: <a href="index.html" accesskey="p" rel="prev">Top</a>, Up: <a href="index.html" accesskey="u" rel="up">Top</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html" title="Index" rel="index">Index</a>]</p>
|
||
|
|
</div>
|
||
|
|
<hr>
|
||
|
|
<span id="Introduction-1"></span><h2 class="chapter">1 Introduction</h2>
|
||
|
|
<p>This manual documents version 3.3.10 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.
|
||
|
|
<span id="index-discrete-Fourier-transform"></span>
|
||
|
|
<span id="index-DFT"></span>
|
||
|
|
</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> log <i>n</i>)
|
||
|
|
algorithms for all lengths, including
|
||
|
|
prime numbers.
|
||
|
|
|
||
|
|
</li><li> FFTW supports arbitrary multi-dimensional data.
|
||
|
|
|
||
|
|
</li><li> FFTW supports the SSE, SSE2, AVX, AVX2, AVX512, KCVI, Altivec, VSX, and
|
||
|
|
NEON vector 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.
|
||
|
|
<span id="index-FFTW"></span>
|
||
|
|
</p>
|
||
|
|
|
||
|
|
<p>In order to use FFTW effectively, you need to learn one basic concept
|
||
|
|
of FFTW’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’s <em>planner</em> “learns” the fastest way to compute the
|
||
|
|
transform on your machine. The planner
|
||
|
|
<span id="index-planner"></span>
|
||
|
|
produces a data structure called a <em>plan</em> that contains this
|
||
|
|
<span id="index-plan"></span>
|
||
|
|
information. Subsequently, the plan is <em>executed</em>
|
||
|
|
<span id="index-execute"></span>
|
||
|
|
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.
|
||
|
|
<span id="index-basic-interface"></span>
|
||
|
|
<span id="index-advanced-interface"></span>
|
||
|
|
<span id="index-guru-interface"></span>
|
||
|
|
</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’s code generator, which produces fast C
|
||
|
|
programs (“codelets”) for any particular array size you may care
|
||
|
|
about.
|
||
|
|
<span id="index-code-generator"></span>
|
||
|
|
<span id="index-codelet"></span>
|
||
|
|
For example, if you need transforms of size
|
||
|
|
513 = 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, “The Design and
|
||
|
|
Implementation of FFTW3,” 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 “A fast Fourier transform
|
||
|
|
compiler”,
|
||
|
|
<span id="index-compiler"></span>
|
||
|
|
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’s algorithm
|
||
|
|
for prime sizes, and a split-radix algorithm (with a
|
||
|
|
“conjugate-pair” variation pointed out to us by Dan Bernstein).
|
||
|
|
FFTW’s code generator also produces new algorithms that we do not
|
||
|
|
completely understand.
|
||
|
|
<span id="index-algorithm"></span>
|
||
|
|
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</a>.
|
||
|
|
Next, <a href="Other-Important-Topics.html">Other Important Topics</a> discusses data alignment
|
||
|
|
(see <a href="SIMD-alignment-and-fftw_005fmalloc.html">SIMD alignment and fftw_malloc</a>),
|
||
|
|
the storage scheme of multi-dimensional arrays
|
||
|
|
(see <a href="Multi_002ddimensional-Array-Format.html">Multi-dimensional Array Format</a>), and FFTW’s mechanism for
|
||
|
|
storing plans on disk (see <a href="Words-of-Wisdom_002dSaving-Plans.html">Words of Wisdom-Saving Plans</a>). Next,
|
||
|
|
<a href="FFTW-Reference.html">FFTW Reference</a> provides comprehensive documentation of all
|
||
|
|
FFTW’s features. Parallel transforms are discussed in their own
|
||
|
|
chapters: <a href="Multi_002dthreaded-FFTW.html">Multi-threaded FFTW</a> and <a href="Distributed_002dmemory-FFTW-with-MPI.html">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</a> and <a href="Calling-FFTW-from-Modern-Fortran.html">Calling FFTW from Modern Fortran</a>. <a href="Installation-and-Customization.html">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</a>. Finally, we thank all the people who helped us in
|
||
|
|
<a href="Acknowledgments.html">Acknowledgments</a>.
|
||
|
|
</p>
|
||
|
|
<hr>
|
||
|
|
<div class="header">
|
||
|
|
<p>
|
||
|
|
Next: <a href="Tutorial.html" accesskey="n" rel="next">Tutorial</a>, Previous: <a href="index.html" accesskey="p" rel="prev">Top</a>, Up: <a href="index.html" accesskey="u" rel="up">Top</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html" title="Index" rel="index">Index</a>]</p>
|
||
|
|
</div>
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
</body>
|
||
|
|
</html>
|