Mercurial > hg > sv-dependency-builds
diff src/fftw-3.3.3/doc/html/Introduction.html @ 10:37bf6b4a2645
Add FFTW3
| author | Chris Cannam |
|---|---|
| date | Wed, 20 Mar 2013 15:35:50 +0000 |
| parents | |
| children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/fftw-3.3.3/doc/html/Introduction.html Wed Mar 20 15:35:50 2013 +0000 @@ -0,0 +1,197 @@ +<html lang="en"> +<head> +<title>Introduction - FFTW 3.3.3</title> +<meta http-equiv="Content-Type" content="text/html"> +<meta name="description" content="FFTW 3.3.3"> +<meta name="generator" content="makeinfo 4.13"> +<link title="Top" rel="start" href="index.html#Top"> +<link rel="prev" href="index.html#Top" title="Top"> +<link rel="next" href="Tutorial.html#Tutorial" title="Tutorial"> +<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage"> +<!-- +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. + --> +<meta http-equiv="Content-Style-Type" content="text/css"> +<style type="text/css"><!-- + pre.display { font-family:inherit } + pre.format { font-family:inherit } + pre.smalldisplay { font-family:inherit; font-size:smaller } + pre.smallformat { font-family:inherit; font-size:smaller } + pre.smallexample { font-size:smaller } + pre.smalllisp { font-size:smaller } + span.sc { font-variant:small-caps } + span.roman { font-family:serif; font-weight:normal; } + span.sansserif { font-family:sans-serif; font-weight:normal; } +--></style> +</head> +<body> +<div class="node"> +<a name="Introduction"></a> +<p> +Next: <a rel="next" accesskey="n" href="Tutorial.html#Tutorial">Tutorial</a>, +Previous: <a rel="previous" accesskey="p" href="index.html#Top">Top</a>, +Up: <a rel="up" accesskey="u" href="index.html#Top">Top</a> +<hr> +</div> + +<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-1"></a><a name="index-DFT-2"></a> + <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>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>FFTW supports arbitrary multi-dimensional data. + + <li>FFTW supports the SSE, SSE2, AVX, Altivec, and MIPS PS instruction + sets. + + <li>FFTW includes parallel (multi-threaded) transforms + for shared-memory systems. +<li>Starting with version 3.3, FFTW includes distributed-memory parallel + transforms using MPI. +</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-3"></a> +<!-- TODO: revise. We don't need to brag any longer --> +<!-- FFTW is usually faster (and sometimes much faster) than all other --> +<!-- freely-available Fourier transform programs found on the Net. It is --> +<!-- competitive with (and often faster than) the FFT codes in Sun's --> +<!-- Performance Library, IBM's ESSL library, HP's CXML library, and --> +<!-- Intel's MKL library, which are targeted at specific machines. --> +<!-- Moreover, FFTW's performance is @emph{portable}. Indeed, FFTW is --> +<!-- unique in that it automatically adapts itself to your machine, your --> +<!-- cache, the size of your memory, your number of registers, and all the --> +<!-- other factors that normally make it impossible to optimize a program --> +<!-- for more than one machine. An extensive comparison of FFTW's --> +<!-- performance with that of other Fourier transform codes has been made, --> +<!-- and the results are available on the Web at --> +<!-- @uref{http://fftw.org/benchfft, the benchFFT home page}. --> +<!-- @cindex benchmark --> +<!-- @fpindex benchfft --> + + <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 <dfn>planner</dfn> “learns” the fastest way to compute the +transform on your machine. The planner +<a name="index-planner-4"></a>produces a data structure called a <dfn>plan</dfn> that contains this +<a name="index-plan-5"></a>information. Subsequently, the plan is <dfn>executed</dfn> +<a name="index-execute-6"></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>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. + <ul> +<li>The <dfn>basic interface</dfn> computes a single + transform of contiguous data. +<li>The <dfn>advanced interface</dfn> computes transforms + of multiple or strided arrays. +<li>The <dfn>guru interface</dfn> supports the most general data + layouts, multiplicities, and strides. +</ul> + 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-7"></a><a name="index-advanced-interface-8"></a><a name="index-guru-interface-9"></a> + + <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 +(2, 3, 5, and 7), 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. +<a name="index-code-generator-10"></a><a name="index-codelet-11"></a>For example, if you need transforms of size +513 = 19*3<sup>3</sup>,you can customize FFTW to support the factor 19 efficiently. + + <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”, +<a name="index-compiler-12"></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>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. +<a name="index-algorithm-13"></a>The reader is referred to the cited papers for the appropriate +references. + + <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'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'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>. + + </body></html> +