Related Readings
- Fast Fourier Transform (local copy)
- Algorithm Design - Section 5.6: Convolutions and Fast Fourier Transform
Introduction
In this post, we present a brief introduction to the fast Fourier transform algorithm and how it can be used to calculate convolutions. We will remove the mathematical details and try to only keep the core algorithm part.
Context
Suppose we have \(n\) data points \( (y_0, y_1, ..., y_{n-1}) \), the problem we want to solve is to calculate the Discrete Fourier Transform:
For each coefficient \(c_k\), it takes \(O(n)\) to compute. As there are \(n\) coefficients to calculate, a naive solution will have \(O(n^2)\) complexity.
Reformulate the Problem
Let \(z = e^{-i2\pi{}/n} \) be the n-th root of unity and \(P(x) = y_0 + y_1 x + ... + y_{n-1}x^{n-1}\). It can be shown that
Now the problem becomes how to evaluate the polynomial \(P\) of degree \(n-1\) at the points of the n-th roots of unity. More specifically, how can we construct the following sequence efficiently?
Divide and Conquer
The Fast Fourier Transform is an elegant algorithm. It illustrates the power of the divide-and-conquer design pattern. To apply the divide-and-conquer technique, we need to find recursive structures in the problem and most importantly, we need to reduce the original problem to a subproblem with a smaller size.
If we look at a polynomial \(Q(x) = a_0 + a_1x + ... + a_m x^{m}\) with \(m\) being an even number. It can be written as
As we can see, the two parts on the right side of the equation are two polynomials of degree m/2 evaluated at \(x^2\). It indicates that there exists a recursive structure in the polynomial representation and calculation.
The Fast Fourier Transform leverages the same idea. Back to our polynomial \(P(x)\), it can be shown that there exist two polynomials of degree \(s-1\), such that
And we have the following recursive structure:

(Note that the "box" represents a collection and the actual order of the items may be different.)
Let \(T(n)\) be the time complexity of the original problem (i.e. evaluating \(P(x)\) at \(n\)-th root of unity ), then we have
The term \(O(n)\) comes from the work of results reordering.
We conclude that the complexity of the Fast Fourier Transform is \(O(n\log{}n)\).
Technical Details
In the lecture note Fast Fourier Transform, the author explains how we can re-order the results. To re-order the results, we need to know the mapping between the index and the exponent:

The author uses the example of index = 6. The binary representation of 6 is 110 and the exponent at index 6 is \((011)_2 = 3\). Note that there is a symmetric structure here: the exponent at index 3 is 6 as highlighted in the figure above.
So how can we establish this relationship?
Let \(\alpha\) denote the odd/even subscript sequence and \(z_{\alpha}\) be the root of unity for that level. Moreover, we assume
The objective is to figure out the relationship between \(B_{\alpha}\) and \(B_{\alpha{},o/e}\). We know that
We also know that
It follows that
Hence,
The above recursive formula tells us that the late \(o\) in the sequence has more contribution to the exponent value. The figure below shows how we construct the exponent value from the index.

Fast Convolution
This section is copied directly from the lecture note:

----- END -----
©2019 - 2022 all rights reserved