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.