Mercurial > hg > batch-feature-extraction-tool

comparison Lib/fftw-3.2.1/doc/html/.svn/text-base/Introduction.html.svn-base @ 0:25bf17994ef1

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