The Fast Fourier Transform Algorithm

The last section on the divide-and-conquer design paradigm on the book Algorithms by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani focuses on a very interesting and well known algorithm: The Fast Fourier Transform algorithm. The Fast Fourier Transform is an algorithm which takes a coefficient representation of a polynomial and changes it to its equivalent point-wise representation. It is widely used in a variety of tasks in computer science such as: getting rid of noise in data, pattern matching, digital filtering, and others.

The big idea in the Fast Fourier Transform algorithm is that a change in the mathematical representation of a problem can simplify and have efficiency benefits over others. To better understand this idea, let’s examine the following polynomial: f(x) = 5 + 2x + x^2. This polynomial has degree 2, and 3 numbers represent it (its coefficients). In general, a polynomial of n - 1 degree has n coefficients. Now, let's investigate what values does this polynomial has at x equals to 0, 1, and 2.

The natural question is then, if n points are given, do these numbers define a polynomial of n - 1 degree? Yes, we can solve a set of linear equations, and the answer will be equal to f(x) = 5 + 2x + x^2. So what does this mean? We have been able to show that a polynomial can be represented in two different ways:

  • A coefficient representation
  • A point-wise representation

The algorithmic steps of the Fast Fourier Transform algorithm takes (assume n is a power of 2):

Re-writes it as:

Then, define new polynomials (the divide step):

And finally, A(w) can be expressed as (the combine step):

The only issue though, is that the points which the algorithm needs to use to compute A(w) for an n (power of 2) need to be carefully chosen. The method the author suggests is using the complex nth-roots of unity. By using the complex nth-roots of unity for an n power of 2, then at successive levels of recursion tree we will have (n/2^k)th roots of unity for k=0, 1, 2, 3, ....

The Fast Fourier Transform Algorithm

Pseudocode:

Implementation:

Tests:

Conclusion

The Fast Fourier Transform algorithm is a really nice way to demonstrate how mathematical ingenuity plays a big role in the design and analysis of algorithms. Changing the representation of the data given to us for a specific task can bring great benefits to both the understanding of the overall process and the efficiency in the computations needed to produce the desired output.