6Fourier transforms
IB Methods
6.9 The fast Fourier transform*
What we’ve said so far is we’ve defined
F (m) =
1
N
N−1
X
j=0
ω
−mj
g(ω
j
).
To compute this directly, even given the values of
ω
−mj
for all
j, m
, this takes
N −
1 additions and
N
+ 1 multiplications. This is 2
N
operations for a single
value of m. To know F (m) for all m, this takes 2N
2
operations.
This is a problem. Historically, during the cold war, especially after the
Cuban missile crisis, people were in fear that the world will one day go into
a huge nuclear war, and something had to be done to prevent this. Thus the
countries decided to come up with a treaty to ensure people don’t perform
nuclear testings anymore.
However, the obvious problem is that we can’t easily check if other countries
are doing nuclear tests. Nuclear tests are easy to spot if the test is done above
ground, since there will be a huge explosion. However, if it is done underground,
it is much harder to test.
They then came up with the idea to put some seismometers all around
the world, and record vibrations in the ground. To distinguish normal crust
movements from nuclear tests, they wanted to take the Fourier transform and
analyze the frequencies of the vibrations. However, they had a large amount of
data, and the value of
N
is on the order of magnitude of a few million. So 2
N
2
will be a huge number that the computers at that time were not able to handle.
So they need to find a trick to perform Fourier transforms quickly. This is known
as the fast Fourier transform. Note that this is nothing new mathematically.
This is entirely a computational trick.
Now suppose N = 2M. We can write
F (m) =
1
2M
2M−1
X
j=0
ω
−jm
g(ω
j
)
=
1
2
"
1
M
M−1
X
k=0
ω
−2km
g(ω
2k
) + ω
−(2k+1)m
g(ω
2k+1
)
#
.
We now let η be an M th root of unity, and define
G(η
k
) = g(ω
2k
), H(η
k
) = g(ω
2k+1
).
We then have
F (m) =
1
2
"
1
M
M−1
X
k=0
η
−km
G(η
k
) +
ω
−m
M
M−1
X
k=0
η
−km
H(η
k
)
#
=
1
2
[
˜
G(m) + ω
−m
˜
H(m)].
Suppose we are given the values of
˜
G
(
m
) and
˜
H
(
m
) and
ω
−m
for all
m
=
{
0
, ··· , N −
1
}
. Then we can compute
F
(
m
) using 3 operations per value of
m
.
So this takes 3 × N = 6M operations for all M.
We can compute
ω
−m
for all
m
using at most 2
N
operations, and suppose it
takes
P
M
operations to compute
˜
G
(
m
) for all
m
. Then the number of operations
needed to compute F (m) is
P
2M
= 2P
M
+ 6M + 2M.
Now let N = 2
n
. Then by iterating this, we can find
P
N
≤ 4N log
2
N N
2
.
So by breaking the Fourier transform apart, we are able to greatly reduce the
number of operations needed to compute the Fourier transform. This is used
nowadays everywhere for everything.