Mercurial > hg > sv-dependency-builds

annotate src/fftw-3.3.5/doc/html/Introduction.html @ 83:ae30d91d2ffe

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Replace these with versions built using an older toolset (so as to avoid ABI compatibilities when linking on Ubuntu 14.04 for packaging purposes)
author Chris Cannam
date Fri, 07 Feb 2020 11:51:13 +0000
parents 2cd0e3b3e1fd
children
rev   line source
Chris@42 1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
Chris@42 2 <html>
Chris@42 3 <!-- This manual is for FFTW
Chris@42 4 (version 3.3.5, 30 July 2016).
Chris@42 5
Chris@42 6 Copyright (C) 2003 Matteo Frigo.
Chris@42 7
Chris@42 8 Copyright (C) 2003 Massachusetts Institute of Technology.
Chris@42 9
Chris@42 10 Permission is granted to make and distribute verbatim copies of this
Chris@42 11 manual provided the copyright notice and this permission notice are
Chris@42 12 preserved on all copies.
Chris@42 13
Chris@42 14 Permission is granted to copy and distribute modified versions of this
Chris@42 15 manual under the conditions for verbatim copying, provided that the
Chris@42 16 entire resulting derived work is distributed under the terms of a
Chris@42 17 permission notice identical to this one.
Chris@42 18
Chris@42 19 Permission is granted to copy and distribute translations of this manual
Chris@42 20 into another language, under the above conditions for modified versions,
Chris@42 21 except that this permission notice may be stated in a translation
Chris@42 22 approved by the Free Software Foundation. -->
Chris@42 23 <!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
Chris@42 24 <head>
Chris@42 25 <title>FFTW 3.3.5: Introduction</title>
Chris@42 26
Chris@42 27 <meta name="description" content="FFTW 3.3.5: Introduction">
Chris@42 28 <meta name="keywords" content="FFTW 3.3.5: Introduction">
Chris@42 29 <meta name="resource-type" content="document">
Chris@42 30 <meta name="distribution" content="global">
Chris@42 31 <meta name="Generator" content="makeinfo">
Chris@42 32 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
Chris@42 33 <link href="index.html#Top" rel="start" title="Top">
Chris@42 34 <link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index">
Chris@42 35 <link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
Chris@42 36 <link href="index.html#Top" rel="up" title="Top">
Chris@42 37 <link href="Tutorial.html#Tutorial" rel="next" title="Tutorial">
Chris@42 38 <link href="index.html#Top" rel="prev" title="Top">
Chris@42 39 <style type="text/css">
Chris@42 40 <!--
Chris@42 41 a.summary-letter {text-decoration: none}
Chris@42 42 blockquote.smallquotation {font-size: smaller}
Chris@42 43 div.display {margin-left: 3.2em}
Chris@42 44 div.example {margin-left: 3.2em}
Chris@42 45 div.indentedblock {margin-left: 3.2em}
Chris@42 46 div.lisp {margin-left: 3.2em}
Chris@42 47 div.smalldisplay {margin-left: 3.2em}
Chris@42 48 div.smallexample {margin-left: 3.2em}
Chris@42 49 div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
Chris@42 50 div.smalllisp {margin-left: 3.2em}
Chris@42 51 kbd {font-style:oblique}
Chris@42 52 pre.display {font-family: inherit}
Chris@42 53 pre.format {font-family: inherit}
Chris@42 54 pre.menu-comment {font-family: serif}
Chris@42 55 pre.menu-preformatted {font-family: serif}
Chris@42 56 pre.smalldisplay {font-family: inherit; font-size: smaller}
Chris@42 57 pre.smallexample {font-size: smaller}
Chris@42 58 pre.smallformat {font-family: inherit; font-size: smaller}
Chris@42 59 pre.smalllisp {font-size: smaller}
Chris@42 60 span.nocodebreak {white-space:nowrap}
Chris@42 61 span.nolinebreak {white-space:nowrap}
Chris@42 62 span.roman {font-family:serif; font-weight:normal}
Chris@42 63 span.sansserif {font-family:sans-serif; font-weight:normal}
Chris@42 64 ul.no-bullet {list-style: none}
Chris@42 65 -->
Chris@42 66 </style>
Chris@42 67
Chris@42 68
Chris@42 69 </head>
Chris@42 70
Chris@42 71 <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
Chris@42 72 <a name="Introduction"></a>
Chris@42 73 <div class="header">
Chris@42 74 <p>
Chris@42 75 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>
Chris@42 76 </div>
Chris@42 77 <hr>
Chris@42 78 <a name="Introduction-1"></a>
Chris@42 79 <h2 class="chapter">1 Introduction</h2>
Chris@42 80 <p>This manual documents version 3.3.5 of FFTW, the
Chris@42 81 <em>Fastest Fourier Transform in the West</em>. FFTW is a comprehensive
Chris@42 82 collection of fast C routines for computing the discrete Fourier
Chris@42 83 transform (DFT) and various special cases thereof.
Chris@42 84 <a name="index-discrete-Fourier-transform"></a>
Chris@42 85 <a name="index-DFT"></a>
Chris@42 86 </p><ul>
Chris@42 87 <li> FFTW computes the DFT of complex data, real data, even-
Chris@42 88 or odd-symmetric real data (these symmetric transforms are usually
Chris@42 89 known as the discrete cosine or sine transform, respectively), and the
Chris@42 90 discrete Hartley transform (DHT) of real data.
Chris@42 91
Chris@42 92 </li><li> The input data can have arbitrary length.
Chris@42 93 FFTW employs <i>O</i>(<i>n</i>&nbsp;log&nbsp;<i>n</i>) algorithms for all lengths, including
Chris@42 94 prime numbers.
Chris@42 95
Chris@42 96 </li><li> FFTW supports arbitrary multi-dimensional data.
Chris@42 97
Chris@42 98 </li><li> FFTW supports the SSE, SSE2, AVX, AVX2, AVX512, KCVI, Altivec, VSX, and
Chris@42 99 NEON vector instruction sets.
Chris@42 100
Chris@42 101 </li><li> FFTW includes parallel (multi-threaded) transforms
Chris@42 102 for shared-memory systems.
Chris@42 103 </li><li> Starting with version 3.3, FFTW includes distributed-memory parallel
Chris@42 104 transforms using MPI.
Chris@42 105 </li></ul>
Chris@42 106
Chris@42 107 <p>We assume herein that you are familiar with the properties and uses of
Chris@42 108 the DFT that are relevant to your application. Otherwise, see
Chris@42 109 e.g. <cite>The Fast Fourier Transform and Its Applications</cite> by E. O. Brigham
Chris@42 110 (Prentice-Hall, Englewood Cliffs, NJ, 1988).
Chris@42 111 <a href="http://www.fftw.org">Our web page</a> also has links to FFT-related
Chris@42 112 information online.
Chris@42 113 <a name="index-FFTW"></a>
Chris@42 114 </p>
Chris@42 115
Chris@42 116 <p>In order to use FFTW effectively, you need to learn one basic concept
Chris@42 117 of FFTW&rsquo;s internal structure: FFTW does not use a fixed algorithm for
Chris@42 118 computing the transform, but instead it adapts the DFT algorithm to
Chris@42 119 details of the underlying hardware in order to maximize performance.
Chris@42 120 Hence, the computation of the transform is split into two phases.
Chris@42 121 First, FFTW&rsquo;s <em>planner</em> &ldquo;learns&rdquo; the fastest way to compute the
Chris@42 122 transform on your machine. The planner
Chris@42 123 <a name="index-planner"></a>
Chris@42 124 produces a data structure called a <em>plan</em> that contains this
Chris@42 125 <a name="index-plan"></a>
Chris@42 126 information. Subsequently, the plan is <em>executed</em>
Chris@42 127 <a name="index-execute"></a>
Chris@42 128 to transform the array of input data as dictated by the plan. The
Chris@42 129 plan can be reused as many times as needed. In typical
Chris@42 130 high-performance applications, many transforms of the same size are
Chris@42 131 computed and, consequently, a relatively expensive initialization of
Chris@42 132 this sort is acceptable. On the other hand, if you need a single
Chris@42 133 transform of a given size, the one-time cost of the planner becomes
Chris@42 134 significant. For this case, FFTW provides fast planners based on
Chris@42 135 heuristics or on previously computed plans.
Chris@42 136 </p>
Chris@42 137 <p>FFTW supports transforms of data with arbitrary length, rank,
Chris@42 138 multiplicity, and a general memory layout. In simple cases, however,
Chris@42 139 this generality may be unnecessary and confusing. Consequently, we
Chris@42 140 organized the interface to FFTW into three levels of increasing
Chris@42 141 generality.
Chris@42 142 </p><ul>
Chris@42 143 <li> The <em>basic interface</em> computes a single
Chris@42 144 transform of contiguous data.
Chris@42 145 </li><li> The <em>advanced interface</em> computes transforms
Chris@42 146 of multiple or strided arrays.
Chris@42 147 </li><li> The <em>guru interface</em> supports the most general data
Chris@42 148 layouts, multiplicities, and strides.
Chris@42 149 </li></ul>
Chris@42 150 <p>We expect that most users will be best served by the basic interface,
Chris@42 151 whereas the guru interface requires careful attention to the
Chris@42 152 documentation to avoid problems.
Chris@42 153 <a name="index-basic-interface"></a>
Chris@42 154 <a name="index-advanced-interface"></a>
Chris@42 155 <a name="index-guru-interface"></a>
Chris@42 156 </p>
Chris@42 157
Chris@42 158 <p>Besides the automatic performance adaptation performed by the planner,
Chris@42 159 it is also possible for advanced users to customize FFTW manually. For
Chris@42 160 example, if code space is a concern, we provide a tool that links only
Chris@42 161 the subset of FFTW needed by your application. Conversely, you may need
Chris@42 162 to extend FFTW because the standard distribution is not sufficient for
Chris@42 163 your needs. For example, the standard FFTW distribution works most
Chris@42 164 efficiently for arrays whose size can be factored into small primes
Chris@42 165 (<em>2</em>, <em>3</em>, <em>5</em>, and <em>7</em>), and otherwise it uses a
Chris@42 166 slower general-purpose routine. If you need efficient transforms of
Chris@42 167 other sizes, you can use FFTW&rsquo;s code generator, which produces fast C
Chris@42 168 programs (&ldquo;codelets&rdquo;) for any particular array size you may care
Chris@42 169 about.
Chris@42 170 <a name="index-code-generator"></a>
Chris@42 171 <a name="index-codelet"></a>
Chris@42 172 For example, if you need transforms of size
Chris@42 173 513&nbsp;=&nbsp;19*3<sup>3</sup>,you can customize FFTW to support the factor <em>19</em> efficiently.
Chris@42 174 </p>
Chris@42 175 <p>For more information regarding FFTW, see the paper, &ldquo;The Design and
Chris@42 176 Implementation of FFTW3,&rdquo; by M. Frigo and S. G. Johnson, which was an
Chris@42 177 invited paper in <cite>Proc. IEEE</cite> <b>93</b> (2), p. 216 (2005). The
Chris@42 178 code generator is described in the paper &ldquo;A fast Fourier transform
Chris@42 179 compiler&rdquo;,
Chris@42 180 <a name="index-compiler"></a>
Chris@42 181 by M. Frigo, in the <cite>Proceedings of the 1999 ACM SIGPLAN Conference
Chris@42 182 on Programming Language Design and Implementation (PLDI), Atlanta,
Chris@42 183 Georgia, May 1999</cite>. These papers, along with the latest version of
Chris@42 184 FFTW, the FAQ, benchmarks, and other links, are available at
Chris@42 185 <a href="http://www.fftw.org">the FFTW home page</a>.
Chris@42 186 </p>
Chris@42 187 <p>The current version of FFTW incorporates many good ideas from the past
Chris@42 188 thirty years of FFT literature. In one way or another, FFTW uses the
Chris@42 189 Cooley-Tukey algorithm, the prime factor algorithm, Rader&rsquo;s algorithm
Chris@42 190 for prime sizes, and a split-radix algorithm (with a
Chris@42 191 &ldquo;conjugate-pair&rdquo; variation pointed out to us by Dan Bernstein).
Chris@42 192 FFTW&rsquo;s code generator also produces new algorithms that we do not
Chris@42 193 completely understand.
Chris@42 194 <a name="index-algorithm"></a>
Chris@42 195 The reader is referred to the cited papers for the appropriate
Chris@42 196 references.
Chris@42 197 </p>
Chris@42 198 <p>The rest of this manual is organized as follows. We first discuss the
Chris@42 199 sequential (single-processor) implementation. We start by describing
Chris@42 200 the basic interface/features of FFTW in <a href="Tutorial.html#Tutorial">Tutorial</a>.
Chris@42 201 Next, <a href="Other-Important-Topics.html#Other-Important-Topics">Other Important Topics</a> discusses data alignment
Chris@42 202 (see <a href="SIMD-alignment-and-fftw_005fmalloc.html#SIMD-alignment-and-fftw_005fmalloc">SIMD alignment and fftw_malloc</a>),
Chris@42 203 the storage scheme of multi-dimensional arrays
Chris@42 204 (see <a href="Multi_002ddimensional-Array-Format.html#Multi_002ddimensional-Array-Format">Multi-dimensional Array Format</a>), and FFTW&rsquo;s mechanism for
Chris@42 205 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,
Chris@42 206 <a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a> provides comprehensive documentation of all
Chris@42 207 FFTW&rsquo;s features. Parallel transforms are discussed in their own
Chris@42 208 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
Chris@42 209 <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
Chris@42 210 install FFTW in your computer system and how to adapt FFTW to your
Chris@42 211 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
Chris@42 212 <a href="Acknowledgments.html#Acknowledgments">Acknowledgments</a>.
Chris@42 213 </p>
Chris@42 214 <hr>
Chris@42 215 <div class="header">
Chris@42 216 <p>
Chris@42 217 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>
Chris@42 218 </div>
Chris@42 219
Chris@42 220
Chris@42 221
Chris@42 222 </body>
Chris@42 223 </html>