1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 The GSL Team.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "GNU General Public License" and "Free Software
Needs Free Documentation", the Front-Cover text being "A GNU Manual",
and with the Back-Cover Text being (a) (see below). A copy of the
license is included in the section entitled "GNU Free Documentation
License".
(a) The Back-Cover Text is: "You have the freedom to copy and modify this
GNU Manual." -->
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Scientific Library – Reference Manual: Mathematical Definitions</title>
<meta name="description" content="GNU Scientific Library – Reference Manual: Mathematical Definitions">
<meta name="keywords" content="GNU Scientific Library – Reference Manual: Mathematical Definitions">
<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="Function-Index.html#Function-Index" rel="index" title="Function Index">
<link href="Fast-Fourier-Transforms.html#Fast-Fourier-Transforms" rel="up" title="Fast Fourier Transforms">
<link href="Overview-of-complex-data-FFTs.html#Overview-of-complex-data-FFTs" rel="next" title="Overview of complex data FFTs">
<link href="Fast-Fourier-Transforms.html#Fast-Fourier-Transforms" rel="previous" title="Fast Fourier Transforms">
<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="Mathematical-Definitions"></a>
<div class="header">
<p>
Next: <a href="Overview-of-complex-data-FFTs.html#Overview-of-complex-data-FFTs" accesskey="n" rel="next">Overview of complex data FFTs</a>, Up: <a href="Fast-Fourier-Transforms.html#Fast-Fourier-Transforms" accesskey="u" rel="up">Fast Fourier Transforms</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Mathematical-Definitions-1"></a>
<h3 class="section">16.1 Mathematical Definitions</h3>
<a name="index-FFT-mathematical-definition"></a>
<p>Fast Fourier Transforms are efficient algorithms for
calculating the discrete Fourier transform (DFT),
</p>
<div class="example">
<pre class="example">x_j = \sum_{k=0}^{n-1} z_k \exp(-2\pi i j k / n)
</pre></div>
<p>The DFT usually arises as an approximation to the continuous Fourier
transform when functions are sampled at discrete intervals in space or
time. The naive evaluation of the discrete Fourier transform is a
matrix-vector multiplication
<em>W\vec{z}</em>. A general matrix-vector multiplication takes
<em>O(n^2)</em> operations for <em>n</em> data-points. Fast Fourier
transform algorithms use a divide-and-conquer strategy to factorize the
matrix <em>W</em> into smaller sub-matrices, corresponding to the integer
factors of the length <em>n</em>. If <em>n</em> can be factorized into a
product of integers
<em>f_1 f_2 ... f_m</em> then the DFT can be computed in <em>O(n \sum
f_i)</em> operations. For a radix-2 FFT this gives an operation count of
<em>O(n \log_2 n)</em>.
</p>
<p>All the FFT functions offer three types of transform: forwards, inverse
and backwards, based on the same mathematical definitions. The
definition of the <em>forward Fourier transform</em>,
<em>x = FFT(z)</em>, is,
</p>
<div class="example">
<pre class="example">x_j = \sum_{k=0}^{n-1} z_k \exp(-2\pi i j k / n)
</pre></div>
<p>and the definition of the <em>inverse Fourier transform</em>,
<em>x = IFFT(z)</em>, is,
</p>
<div class="example">
<pre class="example">z_j = {1 \over n} \sum_{k=0}^{n-1} x_k \exp(2\pi i j k / n).
</pre></div>
<p>The factor of <em>1/n</em> makes this a true inverse. For example, a call
to <code>gsl_fft_complex_forward</code> followed by a call to
<code>gsl_fft_complex_inverse</code> should return the original data (within
numerical errors).
</p>
<p>In general there are two possible choices for the sign of the
exponential in the transform/ inverse-transform pair. GSL follows the
same convention as <small>FFTPACK</small>, using a negative exponential for the forward
transform. The advantage of this convention is that the inverse
transform recreates the original function with simple Fourier
synthesis. Numerical Recipes uses the opposite convention, a positive
exponential in the forward transform.
</p>
<p>The <em>backwards FFT</em> is simply our terminology for an unscaled
version of the inverse FFT,
</p>
<div class="example">
<pre class="example">z^{backwards}_j = \sum_{k=0}^{n-1} x_k \exp(2\pi i j k / n).
</pre></div>
<p>When the overall scale of the result is unimportant it is often
convenient to use the backwards FFT instead of the inverse to save
unnecessary divisions.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Overview-of-complex-data-FFTs.html#Overview-of-complex-data-FFTs" accesskey="n" rel="next">Overview of complex data FFTs</a>, Up: <a href="Fast-Fourier-Transforms.html#Fast-Fourier-Transforms" accesskey="u" rel="up">Fast Fourier Transforms</a> [<a href="Function-Index.html#Function-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
