Computational Physics

A9 The fast Fourier transform 599

transformfˆis also a function defined on discrete points,kn, defined by

kn=

2 nπ

L

, n=0,...,N−1. (A.133)

The Fourier transform reads

ˆf(kn)=

N∑− 1

j= 0

f(xj)e^2 πinj/N. (A.134)

We can also define the backward transform:

f(xj)=

1

L

∑

j

ˆf(kn)e−^2 πinj/N. (A.135)

If the points are not discrete, the Fourier transform is defined for the infinite set
ofk-values 2πn/Lwithn=0,...∞, and the sum over the indexjis replaced by
an integral:

fˆ(kn)=

∫L

0

dxf(x)eiknx. (A.136)

If the function is not periodic,Lgoes to infinity, and the Fourier transform is defined
for every realkas

fˆ(k)=

∫∞

−∞

dxf(x)eikx, (A.137)

with backward transform

f(x)=

1

2 π

∫∞

−∞

dkˆf(k)e−ikx. (A.138)

When Fourier-transforming a nonperiodic function on a computer, it is usually
restricted to a finite interval using discrete points within that interval. Furthermore,
the function is considered to be continued periodically outside this interval. This
restriction to a discrete set combined with periodic continuation should always
be handled carefully. For example, after Fourier-transforming and back again, we
must use the result only on the original interval: extending the solution outside this
interval leads to periodic continuation of our function there. The usual problems
involved in discretisation should be taken care of – seeAppendix A5.

A9.2 How does the FFT work?

To determine the discrete Fourier transform directly, the sum overjis carried out
for eachkn, that is,Ntimes a sum ofNterms has to be calculated, which amounts
to a total number of multiplications/additions ofN^2. In the fast Fourier transform,
it is possible to reduce the work toO(Nlog 2 N)operations. This is an important
difference: for largeN, log 2 Nis much smaller thanN. For example, log 2106 ≈20!