Mercurial > hg > js-dsp-test

annotate fft/fftw/fftw-3.3.4/doc/html/Introduction.html @ 40:223f770b5341 kissfft-double tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Try a double-precision kissfft
author Chris Cannam
date Wed, 07 Sep 2016 10:40:32 +0100
parents 26056e866c29
children
rev   line source
Chris@19 1 <html lang="en">
Chris@19 2 <head>
Chris@19 3 <title>Introduction - FFTW 3.3.4</title>
Chris@19 4 <meta http-equiv="Content-Type" content="text/html">
Chris@19 5 <meta name="description" content="FFTW 3.3.4">
Chris@19 6 <meta name="generator" content="makeinfo 4.13">
Chris@19 7 <link title="Top" rel="start" href="index.html#Top">
Chris@19 8 <link rel="prev" href="index.html#Top" title="Top">
Chris@19 9 <link rel="next" href="Tutorial.html#Tutorial" title="Tutorial">
Chris@19 10 <link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
Chris@19 11 <!--
Chris@19 12 This manual is for FFTW
Chris@19 13 (version 3.3.4, 20 September 2013).
Chris@19 14
Chris@19 15 Copyright (C) 2003 Matteo Frigo.
Chris@19 16
Chris@19 17 Copyright (C) 2003 Massachusetts Institute of Technology.
Chris@19 18
Chris@19 19 Permission is granted to make and distribute verbatim copies of
Chris@19 20 this manual provided the copyright notice and this permission
Chris@19 21 notice are preserved on all copies.
Chris@19 22
Chris@19 23 Permission is granted to copy and distribute modified versions of
Chris@19 24 this manual under the conditions for verbatim copying, provided
Chris@19 25 that the entire resulting derived work is distributed under the
Chris@19 26 terms of a permission notice identical to this one.
Chris@19 27
Chris@19 28 Permission is granted to copy and distribute translations of this
Chris@19 29 manual into another language, under the above conditions for
Chris@19 30 modified versions, except that this permission notice may be
Chris@19 31 stated in a translation approved by the Free Software Foundation.
Chris@19 32 -->
Chris@19 33 <meta http-equiv="Content-Style-Type" content="text/css">
Chris@19 34 <style type="text/css"><!--
Chris@19 35 pre.display { font-family:inherit }
Chris@19 36 pre.format { font-family:inherit }
Chris@19 37 pre.smalldisplay { font-family:inherit; font-size:smaller }
Chris@19 38 pre.smallformat { font-family:inherit; font-size:smaller }
Chris@19 39 pre.smallexample { font-size:smaller }
Chris@19 40 pre.smalllisp { font-size:smaller }
Chris@19 41 span.sc { font-variant:small-caps }
Chris@19 42 span.roman { font-family:serif; font-weight:normal; }
Chris@19 43 span.sansserif { font-family:sans-serif; font-weight:normal; }
Chris@19 44 --></style>
Chris@19 45 </head>
Chris@19 46 <body>
Chris@19 47 <div class="node">
Chris@19 48 <a name="Introduction"></a>
Chris@19 49 <p>
Chris@19 50 Next:&nbsp;<a rel="next" accesskey="n" href="Tutorial.html#Tutorial">Tutorial</a>,
Chris@19 51 Previous:&nbsp;<a rel="previous" accesskey="p" href="index.html#Top">Top</a>,
Chris@19 52 Up:&nbsp;<a rel="up" accesskey="u" href="index.html#Top">Top</a>
Chris@19 53 <hr>
Chris@19 54 </div>
Chris@19 55
Chris@19 56 <h2 class="chapter">1 Introduction</h2>
Chris@19 57
Chris@19 58 <p>This manual documents version 3.3.4 of FFTW, the
Chris@19 59 <em>Fastest Fourier Transform in the West</em>. FFTW is a comprehensive
Chris@19 60 collection of fast C routines for computing the discrete Fourier
Chris@19 61 transform (DFT) and various special cases thereof.
Chris@19 62 <a name="index-discrete-Fourier-transform-1"></a><a name="index-DFT-2"></a>
Chris@19 63 <ul>
Chris@19 64 <li>FFTW computes the DFT of complex data, real data, even-
Chris@19 65 or odd-symmetric real data (these symmetric transforms are usually
Chris@19 66 known as the discrete cosine or sine transform, respectively), and the
Chris@19 67 discrete Hartley transform (DHT) of real data.
Chris@19 68
Chris@19 69 <li>The input data can have arbitrary length.
Chris@19 70 FFTW employs <i>O</i>(<i>n</i>&nbsp;log&nbsp;<i>n</i>) algorithms for all lengths, including
Chris@19 71 prime numbers.
Chris@19 72
Chris@19 73 <li>FFTW supports arbitrary multi-dimensional data.
Chris@19 74
Chris@19 75 <li>FFTW supports the SSE, SSE2, AVX, Altivec, and MIPS PS instruction
Chris@19 76 sets.
Chris@19 77
Chris@19 78 <li>FFTW includes parallel (multi-threaded) transforms
Chris@19 79 for shared-memory systems.
Chris@19 80 <li>Starting with version 3.3, FFTW includes distributed-memory parallel
Chris@19 81 transforms using MPI.
Chris@19 82 </ul>
Chris@19 83
Chris@19 84 <p>We assume herein that you are familiar with the properties and uses of
Chris@19 85 the DFT that are relevant to your application. Otherwise, see
Chris@19 86 e.g. <cite>The Fast Fourier Transform and Its Applications</cite> by E. O. Brigham
Chris@19 87 (Prentice-Hall, Englewood Cliffs, NJ, 1988).
Chris@19 88 <a href="http://www.fftw.org">Our web page</a> also has links to FFT-related
Chris@19 89 information online.
Chris@19 90 <a name="index-FFTW-3"></a>
Chris@19 91 <!-- TODO: revise. We don't need to brag any longer -->
Chris@19 92 <!-- FFTW is usually faster (and sometimes much faster) than all other -->
Chris@19 93 <!-- freely-available Fourier transform programs found on the Net. It is -->
Chris@19 94 <!-- competitive with (and often faster than) the FFT codes in Sun's -->
Chris@19 95 <!-- Performance Library, IBM's ESSL library, HP's CXML library, and -->
Chris@19 96 <!-- Intel's MKL library, which are targeted at specific machines. -->
Chris@19 97 <!-- Moreover, FFTW's performance is @emph{portable}. Indeed, FFTW is -->
Chris@19 98 <!-- unique in that it automatically adapts itself to your machine, your -->
Chris@19 99 <!-- cache, the size of your memory, your number of registers, and all the -->
Chris@19 100 <!-- other factors that normally make it impossible to optimize a program -->
Chris@19 101 <!-- for more than one machine. An extensive comparison of FFTW's -->
Chris@19 102 <!-- performance with that of other Fourier transform codes has been made, -->
Chris@19 103 <!-- and the results are available on the Web at -->
Chris@19 104 <!-- @uref{http://fftw.org/benchfft, the benchFFT home page}. -->
Chris@19 105 <!-- @cindex benchmark -->
Chris@19 106 <!-- @fpindex benchfft -->
Chris@19 107
Chris@19 108 <p>In order to use FFTW effectively, you need to learn one basic concept
Chris@19 109 of FFTW's internal structure: FFTW does not use a fixed algorithm for
Chris@19 110 computing the transform, but instead it adapts the DFT algorithm to
Chris@19 111 details of the underlying hardware in order to maximize performance.
Chris@19 112 Hence, the computation of the transform is split into two phases.
Chris@19 113 First, FFTW's <dfn>planner</dfn> &ldquo;learns&rdquo; the fastest way to compute the
Chris@19 114 transform on your machine. The planner
Chris@19 115 <a name="index-planner-4"></a>produces a data structure called a <dfn>plan</dfn> that contains this
Chris@19 116 <a name="index-plan-5"></a>information. Subsequently, the plan is <dfn>executed</dfn>
Chris@19 117 <a name="index-execute-6"></a>to transform the array of input data as dictated by the plan. The
Chris@19 118 plan can be reused as many times as needed. In typical
Chris@19 119 high-performance applications, many transforms of the same size are
Chris@19 120 computed and, consequently, a relatively expensive initialization of
Chris@19 121 this sort is acceptable. On the other hand, if you need a single
Chris@19 122 transform of a given size, the one-time cost of the planner becomes
Chris@19 123 significant. For this case, FFTW provides fast planners based on
Chris@19 124 heuristics or on previously computed plans.
Chris@19 125
Chris@19 126 <p>FFTW supports transforms of data with arbitrary length, rank,
Chris@19 127 multiplicity, and a general memory layout. In simple cases, however,
Chris@19 128 this generality may be unnecessary and confusing. Consequently, we
Chris@19 129 organized the interface to FFTW into three levels of increasing
Chris@19 130 generality.
Chris@19 131 <ul>
Chris@19 132 <li>The <dfn>basic interface</dfn> computes a single
Chris@19 133 transform of contiguous data.
Chris@19 134 <li>The <dfn>advanced interface</dfn> computes transforms
Chris@19 135 of multiple or strided arrays.
Chris@19 136 <li>The <dfn>guru interface</dfn> supports the most general data
Chris@19 137 layouts, multiplicities, and strides.
Chris@19 138 </ul>
Chris@19 139 We expect that most users will be best served by the basic interface,
Chris@19 140 whereas the guru interface requires careful attention to the
Chris@19 141 documentation to avoid problems.
Chris@19 142 <a name="index-basic-interface-7"></a><a name="index-advanced-interface-8"></a><a name="index-guru-interface-9"></a>
Chris@19 143
Chris@19 144 <p>Besides the automatic performance adaptation performed by the planner,
Chris@19 145 it is also possible for advanced users to customize FFTW manually. For
Chris@19 146 example, if code space is a concern, we provide a tool that links only
Chris@19 147 the subset of FFTW needed by your application. Conversely, you may need
Chris@19 148 to extend FFTW because the standard distribution is not sufficient for
Chris@19 149 your needs. For example, the standard FFTW distribution works most
Chris@19 150 efficiently for arrays whose size can be factored into small primes
Chris@19 151 (2, 3, 5, and 7), and otherwise it uses a
Chris@19 152 slower general-purpose routine. If you need efficient transforms of
Chris@19 153 other sizes, you can use FFTW's code generator, which produces fast C
Chris@19 154 programs (&ldquo;codelets&rdquo;) for any particular array size you may care
Chris@19 155 about.
Chris@19 156 <a name="index-code-generator-10"></a><a name="index-codelet-11"></a>For example, if you need transforms of size
Chris@19 157 513&nbsp;=&nbsp;19*3<sup>3</sup>,you can customize FFTW to support the factor 19 efficiently.
Chris@19 158
Chris@19 159 <p>For more information regarding FFTW, see the paper, &ldquo;The Design and
Chris@19 160 Implementation of FFTW3,&rdquo; by M. Frigo and S. G. Johnson, which was an
Chris@19 161 invited paper in <cite>Proc. IEEE</cite> <b>93</b> (2), p. 216 (2005). The
Chris@19 162 code generator is described in the paper &ldquo;A fast Fourier transform
Chris@19 163 compiler&rdquo;,
Chris@19 164 <a name="index-compiler-12"></a>by M. Frigo, in the <cite>Proceedings of the 1999 ACM SIGPLAN Conference
Chris@19 165 on Programming Language Design and Implementation (PLDI), Atlanta,
Chris@19 166 Georgia, May 1999</cite>. These papers, along with the latest version of
Chris@19 167 FFTW, the FAQ, benchmarks, and other links, are available at
Chris@19 168 <a href="http://www.fftw.org">the FFTW home page</a>.
Chris@19 169
Chris@19 170 <p>The current version of FFTW incorporates many good ideas from the past
Chris@19 171 thirty years of FFT literature. In one way or another, FFTW uses the
Chris@19 172 Cooley-Tukey algorithm, the prime factor algorithm, Rader's algorithm
Chris@19 173 for prime sizes, and a split-radix algorithm (with a
Chris@19 174 &ldquo;conjugate-pair&rdquo; variation pointed out to us by Dan Bernstein).
Chris@19 175 FFTW's code generator also produces new algorithms that we do not
Chris@19 176 completely understand.
Chris@19 177 <a name="index-algorithm-13"></a>The reader is referred to the cited papers for the appropriate
Chris@19 178 references.
Chris@19 179
Chris@19 180 <p>The rest of this manual is organized as follows. We first discuss the
Chris@19 181 sequential (single-processor) implementation. We start by describing
Chris@19 182 the basic interface/features of FFTW in <a href="Tutorial.html#Tutorial">Tutorial</a>.
Chris@19 183 Next, <a href="Other-Important-Topics.html#Other-Important-Topics">Other Important Topics</a> discusses data alignment
Chris@19 184 (see <a href="SIMD-alignment-and-fftw_005fmalloc.html#SIMD-alignment-and-fftw_005fmalloc">SIMD alignment and fftw_malloc</a>),
Chris@19 185 the storage scheme of multi-dimensional arrays
Chris@19 186 (see <a href="Multi_002ddimensional-Array-Format.html#Multi_002ddimensional-Array-Format">Multi-dimensional Array Format</a>), and FFTW's mechanism for
Chris@19 187 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@19 188 <a href="FFTW-Reference.html#FFTW-Reference">FFTW Reference</a> provides comprehensive documentation of all
Chris@19 189 FFTW's features. Parallel transforms are discussed in their own
Chris@19 190 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@19 191 <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@19 192 install FFTW in your computer system and how to adapt FFTW to your
Chris@19 193 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@19 194 <a href="Acknowledgments.html#Acknowledgments">Acknowledgments</a>.
Chris@19 195
Chris@19 196 </body></html>
Chris@19 197