# The fast Fourier transform

By Marcus Wilson 20/06/2012

I made the brave decision yesterday to attend a seminar in the Computer Science department. I used to like computer science as a teenager – I was one of those geeks who wrote their own computer games – but in latter times I’ve stuck with the physics and used computers begrudgingly as a means of doing my mathematical calculations.

And my preconceptions were partly justified, as it was a little bit geeky. But it was also pretty interesting. The seminar concerned the numerical implementation of the Fourier Transform (FT). This is a piece of maths that is incredibly useful in physics. It arises in fields as diverse as image processing, optics, solid-state physics, thermodynamics, particle physics, astronomy; even my brain dynamics work uses a lot of Fourier Transforms.  FTs are used to a vast extent in telecommunications. I hope you get the picture that they are really useful things and physics wouldn’t be the same without them.

I won’t go into detail about what a FT is, but in short it involves describing a signal as a sum of waves of different frequencies. Doing this can make problems in physics a whole lot easier. Now, computing a FT, although simple in concept, is not a trivial undertaking. It takes a lot of CPU time. It was estimated by Cray that in 1990 some 40% of its super-computer cycles were spent on calculating FTs for one application or another. There has been a huge amount of research dedicated to speeding up the calculation of FTs.  This seminar, by  PhD student Antony Blake, showed an improved method. He nicely presented some plots which showed his implementation of the FT was, generally speaking, better than other products in existence. Well done the student! It shows if nothing else that PhD students can take on the world when it comes to research, and win.

One amusing factoid that Antony mentioned was on the history of the bulk-standard fast Fourier Transform algorithm, invented by Cooley and Tukey in 1965. At the time, this implementation was of great significance, since it was quick (hence the name ‘Fast Fourier Transform’), and allowed one to handle large sets of data.  However, a bit of delving into archives showed that it wasn’t Cooley and Tukey who first used the algorithm – it was Carl Friedrich Gauss, in 1805, who used it for astronomical calculations even before Joseph Fourier had formulated the transform that bears his name! In Gauss’ case, his use of it was even more remarkable, since he had to do the calculations by hand!  Gauss was one of those insanely clever mathematicians who only come around once a century or so.