Today in Edworking News we want to talk about Convolutions, Fast Fourier Transform and Polynomials.
You may remember from high school what a polynomial is. If so, you may also remember how to multiply two of them. But what if I told you that the method you were taught is slow as F? In this post we will connect polynomials with the Fourier Transform and convolutions, and show you how to multiply polynomials with $O(nlogn)$ complexity instead of $O(n^2)$, being the latter the method that’s taught in high school.
Polynomials: A Quick Recap
Let's do a quick recap on what polynomials are. Formally defined, a polynomial $P(x)$ is a sum of terms where each one is an indeterminate variable $x$ with some exponent $k$ multiplied by a coefficient $a_k$. This is an example of a polynomial. Note that we say it has a degree 2 since it is its maximum exponent. It can be expressed as a vector like [5, 2, 9] or [9, 2, 5] depending on the notation we use. Let $P(x)$ and $Q(x)$ be two polynomials, we can perform different operations with them, like adding or subtracting them. In both cases, the result is trivially computed by summing (or subtracting) each term individually.
```python
from itertools import zip_longest
def add_poly(p, q):
return [sum(t) for t in zip_longest(p, q, fillvalue=0)]
Convolutions
Before answering the question if we can do better than $O(n^2)$ to multiply polynomials, let's introduce the concept of convolution, since it will come in handy to understand what’s next. Convolution is defined both in continuous and discrete domains. The continuous domain might be cool for mathematicians, but we engineers who do real things prefer the discrete domain.
We can define the convolution in the discrete domain of two discrete signals $p$ and $q$ as:
```math
(p * q)[n] = \sum_{m=-\infty}^{\infty} p[m] q[n - m]
The operation is rather simple. You just need to flip $q$ and sum the product of all elements that overlap with $p$. Trust me, it's easier than it looks. Let's say we have two discrete signals $p$ and $q$ represented as vectors:
```python
p = [1, 2, 3]
q = [0, 1, 0.5]
Let's calculate the convolution of both $p q$. Note that $$ here is the convolution of both signals. You can visualize it step by step as explained in the article.
Visual representation of convolution process.
Fourier Transform, and the FFT
The Fourier Transform is a very powerful transformation that allows converting a signal from time domain to frequency domain. It's some kind of base change, where instead of looking at the signal from a time perspective, we look at it from a frequency point of view. Instead of saying that the signal has $x_1$ value at $t_1$ time, and $x_2$ at $t_2$, etc, we say that the signal is made of different oscillating frequencies at different rates.
These oscillating frequencies are represented with sines and cosines and have a coefficient and a phase attached to them. Every signal that you can imagine can be expressed as the sum of sines and cosines. The only problem is to know which sines/cosines represent that signal.
```python
import numpy as np
import matplotlib.pyplot as plt
Example with a 5 Hz sinusoidal signal
t = np.linspace(0, 1, 500)
signal = np.sin(2 np.pi 5 * t)
fft_result = np.fft.fft(signal)
fft_freq = np.fft.fftfreq(len(signal), d=t[1] - t[0])
plt.plot(fft_freq, np.abs(fft_result))
plt.title('FFT of a 5 Hz sinusoidal signal')
plt.xlabel('Frequency (Hz)')
plt.ylabel('Magnitude')
plt.show()
Multiplying Polynomials Faster
As a quick recap, the way to multiply polynomials that you learned in high school is very inefficient and has a $O(n^2)$ complexity, where $n$ is the degree of the polynomials. This means that multiplying two polynomials of order 100 is way more difficult than order 20. This doesn’t scale for huge polynomials.
But we have an alternative:
Using FFT:
```python
def multiply_fft(p, q):
n = len(p) + len(q) - 1
P = np.fft.fft(p, n)
Q = np.fft.fft(q, n)
return np.fft.ifft(P * Q).real.round().astype(int)
It may seem like a lot of operations, but for large polynomials, this is way faster than the naive method that you were taught in high school.
Benchmark results showing efficiency of FFT method.
```python
import time
Define polynomials
p = np.random.randint(0, 10, 500)
q = np.random.randint(0, 10, 500)
Time naive method
start = time.time()
result_naive = multiply_naive(p, q)
end = time.time()
print('Naive Method Time:', end - start)
Time FFT method
start = time.time()
result_fft = multiply_fft(p, q)
end = time.time()
print('FFT Method Time:', end - start)
Summary
Let’s summarise what we have seen:
Polynomials can be added or subtracted easily.
Multiplication of polynomials using the high school method is inefficient.
Convolutions offer a mathematical way to simplify polynomial multiplication.
The Fourier Transform and FFT offer a method to multiply polynomials with $O(nlogn)$ complexity.
Remember these 3 key ideas for your startup:
Increase Efficiency: Using advanced algorithms like FFT can drastically speed up calculations, saving time and computational resources. This efficiency can be crucial in data-heavy startup environments.
Harness Convolutions: Understanding and leveraging operations like convolutions can simplify complex mathematical tasks. For startups focusing on AI and machine learning, this can significantly optimize processes.
Adopt Modern Tools: Keeping updated with modern computational tools and techniques can provide a competitive edge. Fast multiplication techniques can be integrated into various applications, enhancing performance.
Edworking is a FREE superapp of productivity that includes all you need for work powered by AI in the same superapp, connecting Task Management, Docs, Chat, Videocall, and File Management. Save money today by not paying for Slack, Trello, Dropbox, Zoom, and Notion. For more details, see the original source.
