8.2 THE
FOURIER
TRANSFORM
219
where we have redefined the new 1to be .J2rcN/ T times the old
j.
Discrete
Fourier
transforms
areused extensively in numerical calculation of
problems in which ordinary Fourier transforms are used. For instance, if a dif-
ferential equation lends itselfto a solution via the Fourier transform as discussed
before, then discrete Fourier transforms will give a procedure for fiuding the so-
lution uumerically. Similarly, the frequeucy analysis of signals is nicely handled
by discrete Fourier transforms.
It turns out that discrete Fourieranalysis is very iuteusive computationally. Its
present status as a popular tool iu computational physics is due primarily to a very
fast
Fourier
efficieut method
of
calculatiou known as the
fast
Fourier
transform.
10a typical
transform
Fouriertransform, one has to perform a sum of N terms for every point. Since there
are
N points to transform, the total computational time will be of order N
2
•
10the
fast Fourier transform, one takes
N to be even and divides the sum into two other
sums,one overtheeventermsandone overthe odd
terms.
Thenthecomputation
time will be of order 2 x
(N
/2)2,
or
half
the original calculation. Similarly,
if
N
/2
is even, one can further divide the odd and even sums by two and obtain a
computationtime of4 x (N/4)2, or aquarter
of
the originalcalculation. 10general,
if N
= 2
k
, then by dividing the sums consecutively, we end up with N transforms
to be performed after k steps. So, the computation time will be
kN
= N log2 N.
For
N = 128, the computation time will be 100log2 128 = 700 as opposed to
128
2
R<16,400, a reduction by a factor of over 20. The fast Fourier transformis
indeed fast!
8.2.3 The Fourier Transformof a Distribution
Although one can define the Fourier transform
of
a distribution in exact analogy
to an ordinaryfunction, sometimes it is convenient to define the Fourier transform
of the distribution as a linearfunctional.
Let us ignore the distinction between the two variables
x and k, and simply
define the Fourier transform of a function
f :
JR
--->
JR
as
- 1 1
00
. t
f(u)
= = f(t)e'U
dt.
'\! 2rc
-00
Now we consider two functions, f and g, and note that
1
00
100
1 1
00
.
(j,
g)
==
f(u)g(u)du
=
f(u)
[=
g(t)e-'U'dt]
du
-00 -00
v2n-00
1
00
1 1
00
.]
=
g(t)
[--
f(u)e-'U'du
dt
-00
../iii-oo
=
L:
g(t)l(t)
dt
=
(I,
g) .
The following definition is motivated by the last equation.