### 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