One of the most useful mathematical techniques ever invented is called
the Fourier Transform. To motivate this, imagine that you are
listening to a concert, and that you record the intensity of the sound u(t)
of the orchestra as a function of the time t. The orchestra is
composed of instruments that all make sounds of a frequency \omega with
each such sound having an intensity U(\omega).
A sound of frequency \omega has the mathematical
expression
e^{i \omega t}
where i is the square-root of -1. The total sound that
we hear is the combination of all of these sounds and it can be expressed
as an integral in the form
u(t) = \frac{1}{2\pi}\int^\infty_{-\infty}U(\omega)e^{i \omega t}\
d\omega
This integral which links the two functions U(\omega) and u(t),
is called the Inverse Fourier Transform after the French mathematician
Fourier. Remarkably, it is easy to find the inverse to this process. This
is called the Fourier Transform and it is given by
U(\omega) = \int^\infty_{-\infty} u(t) e^{-i \omega t}\ dt
The Fourier Transform has countless applications ranging from telecommunications
to crystallography, from speech recognition to astronomy, from Radar to
mobile phones, and from meteorology to archaeology. It even has important
applications in cryptography. The whole signal processing industry (indeed
much of the digital revolution) owes its existence to the Fourier Transform.
The reason is that it links the intensity of a function to the waves that
make it up. As so much of what we do involves sound or light waves, the
applications are universal. It is so important that calculating the Fourier
Transform was one of the first tasks given to the early computers in use
in the 1960s.
However, these implementations had a lot of difficulties in calculating
the Fourier Transform and were so slow that they were absorbing a huge
amount of computing time. Roughly speaking if you wanted to find the values
of the Fourier Transform at N points then you had to do N^2 calculations.
Unfortunately, for accuracy you have to take large values of N which
means that N^2 is very large, too large to make it possible
to calculate easily. However, in 1965 there was a remarkable breakthrough
when a technique called the Fast Fourier Transform or
FFT was invented to evaluate the Fourier Transform. This was much faster,
taking a time proportional to N \mbox{ log}{(N)} which is a lot
smaller than N^2. With the FFT available to calculate
the Fourier Transform quickly, its applications became almost unlimited.
