Every Intuition Behind Fourier Transform

There is not a direct relationship between Fourier Transform and the multiplication of numbers. Let me guide you through it:

The complexity of multiplication is $N^2$ (N is the generalization of digit amount, and we do N^2 multiplications to multiply two N-digit numbers).

Now, the good part, multiplication in polynomial point-value form (be patient, Iβll explain what this is in detail shortly) takes only $N$ computations instead of $N^2$.

If we somehow can represent our number in polynomial form, and turn it into point-value form, then we should be able to do the multiplication in complexity of $N$ instead of $N^2$.

As stated before, the complexity of multiplication is $N^2$. However, the complexity of multiplication for polynomials, in ** point-value form**, is $N$.

WOW!

But what is point-value form?

Recap on point-value/coefficient form (start)

*If you feel like you donβt need this recap, feel free to skip till you see Recap on point-value/coefficient form (end)*.

An example polynomial: $3x^2 + 2x + 5$

Coefficient form (the most popular one): we just denote the coefficients. For our example above, the coefficient form would be:

$3, 2, 5$How to construct a polynomial from coefficient form? It is pretty straightforward:

$3x^2 + 2x^1 + 5x^0 = 3x^2 + 2x + 5$Point-value form is a bit more different. The above polynomial example is degree 2 (the highest power of `x`

). If we give 3 points on this polynomial, there wonβt be any other degree 2 polynomial that passes from these 3 points. In short, if there is `n+1`

points, there can be only one polynomial of degree `n`

that satisfies these points. The points will be `x`

and `y`

pairs in this case.

You can check it for yourself; when you plug `1`

, the polynomial spits out `10`

. And so onβ¦

Recap on point-value/coefficient form (end)

Here is a showcase of multiplying two polynomials in point-value form:

- 1st polynomial: $x^2 + 1$
- 2nd polynomial: $2x^2 + 2$
- 3rd polynomial (what should we get by multiplying the above two): $2x^4 + 4x^2 + 2$

The resulting polynomial is of degree `4`

. So, we will need at least `5`

points to be able to represent that polynomial in point-value form.

Letβs pick `5`

points each from our 1st and 2nd polynomial.

- 5 points for polynomial: $x^2 + 1$:
- (0, 1), (1, 2), (2, 5), (3, 10), (4, 17)

- 5 points for polynomial $2x^2 + 2$:
- (0, 2), (1, 4), (2, 10), (3, 20), (4, 34)

Letβs multiply the `y`

values of the points that share the same `x`

value.

If you plug these points we just calculated, into the 3rd polynomial, youβll see they will satisfy the equation.

- Have 2 numbers to multiply
- Treat these numbers as the coefficient representation of a polynomial
- Compute the point-value form of these 2 polynomials
- Multiply these 2 polynomials in point-value form
- Convert the resulting polynomial back into coefficient form
- Here is the result of your multiplication!

I will use the same example from our `multiplication in point-value form`

, so that it would be easier to follow:

- 11 and 22
- $x^2 + 1$ for
`11`

,

$2x^2 + 2$ for`22`

- (0, 1), (1, 2), (2, 5), (3, 10), (4, 17) for
`11`

, (0, 2), (1, 4), (2, 10), (3, 20), (4, 34) for`22`

- Point-value form: (0, 2), (1, 8), (2, 50), (3, 200), (4, 578)
- Coefficient form: $2x^4 + 4x^2 + 2$
- 242 = 11 x 22 indeed!

Our astute readers may realize that we may have reduced the complexity of multiplication to $N$ from $N^2$, but now we have another problem. The complexity of computing the ** point-value form** from the

Here is where the magic happens. DFT can convert from `coefficient form`

to `point-value form`

(and vice versa). And if we follow a specific algorithm (FFT) to compute DFT, we can do this computation in $N\log(N)$. Effectively, we will be able to multiply two numbers in $N\log(N)$.

It is amazing that with this very same formula we used for wave decomposition:

$\sum_{n=0}^{N-1} g_ne^{-ikn2\pi/N}$we are able to convert between coefficient and point-value form of polynomials. In this form, itβs not easy to see why this formula will be able to convert from coefficient and point-value form. Iβll help you.

First, a formal definition of a polynomial:

$A(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \ldots + a_{N-1}x^{N-1}$In this definition, `A(x)`

is the polynomial, whose coefficients are given by `a`

.

Recall the DFT formula, when we were inspecting waves, `g`

was representing the time-domain. We are not dealing with waves in here; letβs rename the `g`

into `a`

.

Letβs define:

$\omega_N = e^{-i2\pi / N}$So, we can rewrite our DFT formula as:

$\sum_{n=0}^{N-1}a_n\omega_N^{kn}$We are very close! As the last step, letβs make one more abstraction:

$\omega_N^k = x$And voila!

$\sum_{n=0}^{N-1}a_nx^n$This formula is actually equal to the definition of a polynomial we gave above! Recall:

$A(x) = a_0x^0 + a_1x^1 + a_2x^2 + a_3x^3 + \ldots + a_{N-1}x^{N-1}$So:

$A(x) = \sum_{n=0}^{N-1}a_nx^n$Now, you probably have the question about this equation:

$x = e^{-ik2\pi/N}$At first glance, `decomposing a wave`

and `transitioning between coefficient to point-value form`

, seem to be very unrelated. But if they share the exact same formula, they should be sharing a very common intuition behind all these.

I have a great answer on why `decomposing a wave`

and `transitioning between coefficient to point-value form`

are nearly identical.

Recall these transformations from `point-value form`

to `coefficient form`

from above:

- Point-value: (0, 2), (1, 8), (2, 50), (3, 200), (4, 578)
- Coefficient: $2x^4 + 4x^2 + 2$

What we are doing is, inputting some points from the polynomial, and outputting the formula of the polynomial.

We can say the same for decomposing waves. We are inputting some data points from the wave, and getting back the formula of the wave (amplitudes and phases of the sine waves in it).

Of course, the above explanation is an oversimplification that misses some details. But it really is the intuition behind all these:

By using the data points from a complex function, deducing what the actual complex function is.

If you want to see a working example where we get $2x^4 + 4x^2 + 2$ by multiplying $x^2 + 1$ and $2x^2 + 2$, try to run this Python code (taken from here):

```
import numpy
from numpy.fft import fft, ifft
def poly_mul(p1, p2):
"""Multiply two polynomials.
p1 and p2 are arrays of coefficients in degree-increasing order.
"""
deg1 = p1.shape[0] - 1
deg2 = p1.shape[0] - 1
# Would be 2*(deg1 + deg2) + 1, but the next-power-of-2 handles the +1
total_num_pts = 2 * (deg1 + deg2)
next_power_of_2 = 1 << (total_num_pts - 1).bit_length()
ff_p1 = fft(numpy.pad(p1, (0, next_power_of_2 - p1.shape[0])))
ff_p2 = fft(numpy.pad(p2, (0, next_power_of_2 - p2.shape[0])))
product = ff_p1 * ff_p2
inverted = ifft(product)
rounded = numpy.round(numpy.real(inverted)).astype(numpy.int32)
return numpy.trim_zeros(rounded, trim='b')
p1 = numpy.array([1, 0, 1])
p2 = numpy.array([2, 0, 2])
print(poly_mul(p1, p2))
```

This is just a sneak peak. We will dive into details of FFT, and derive it ourselves in the next post!

To some people, the above explanations might have already rung a bell: `convolution`

. Convolution is basically the combination of two functions to create a third function. However, I wonβt dive into that. This post has already become too long. Iβm just showing the curious readers the way.