Mercurial > hg > sv-dependency-builds
diff src/fftw-3.3.5/doc/html/Introduction.html @ 127:7867fa7e1b6b
Current fftw source
| author | Chris Cannam <cannam@all-day-breakfast.com> |
|---|---|
| date | Tue, 18 Oct 2016 13:40:26 +0100 |
| parents | |
| children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/fftw-3.3.5/doc/html/Introduction.html Tue Oct 18 13:40:26 2016 +0100 @@ -0,0 +1,223 @@ +<!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.5, 30 July 2016). + +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 5.2, http://www.gnu.org/software/texinfo/ --> +<head> +<title>FFTW 3.3.5: Introduction</title> + +<meta name="description" content="FFTW 3.3.5: Introduction"> +<meta name="keywords" content="FFTW 3.3.5: Introduction"> +<meta name="resource-type" content="document"> +<meta name="distribution" content="global"> +<meta name="Generator" content="makeinfo"> +<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> +<link href="index.html#Top" rel="start" title="Top"> +<link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index"> +<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents"> +<link href="index.html#Top" rel="up" title="Top"> +<link href="Tutorial.html#Tutorial" rel="next" title="Tutorial"> +<link href="index.html#Top" rel="prev" title="Top"> +<style type="text/css"> +<!-- +a.summary-letter {text-decoration: none} +blockquote.smallquotation {font-size: smaller} +div.display {margin-left: 3.2em} +div.example {margin-left: 3.2em} +div.indentedblock {margin-left: 3.2em} +div.lisp {margin-left: 3.2em} +div.smalldisplay {margin-left: 3.2em} +div.smallexample {margin-left: 3.2em} +div.smallindentedblock {margin-left: 3.2em; font-size: smaller} +div.smalllisp {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} +pre.smalldisplay {font-family: inherit; font-size: smaller} +pre.smallexample {font-size: smaller} +pre.smallformat {font-family: inherit; font-size: smaller} +pre.smalllisp {font-size: smaller} +span.nocodebreak {white-space:nowrap} +span.nolinebreak {white-space:nowrap} +span.roman {font-family:serif; font-weight:normal} +span.sansserif {font-family:sans-serif; font-weight:normal} +ul.no-bullet {list-style: none} +--> +</style> + + +</head> + +<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000"> +<a name="Introduction"></a> +<div class="header"> +<p> +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> [<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> +</div> +<hr> +<a name="Introduction-1"></a> +<h2 class="chapter">1 Introduction</h2> +<p>This manual documents version 3.3.5 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"></a> +<a name="index-DFT"></a> +</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. +<a name="index-FFTW"></a> +</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 +<a name="index-planner"></a> +produces a data structure called a <em>plan</em> that contains this +<a name="index-plan"></a> +information. Subsequently, the plan is <em>executed</em> +<a name="index-execute"></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> +<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. +<a name="index-basic-interface"></a> +<a name="index-advanced-interface"></a> +<a name="index-guru-interface"></a> +</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. +<a name="index-code-generator"></a> +<a name="index-codelet"></a> +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”, +<a name="index-compiler"></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> +<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"></a> +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">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>. +</p> +<hr> +<div class="header"> +<p> +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> [<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> +</div> + + + +</body> +</html>