# Parallel/Distributed FFT
## Parallel FFT
Suppose we are given a polynomial $$P(X) = \sum\_{i=0}^{2^{2n} - 1} c\_i X^i$$. The Discrete Fourier Transform (DFT) of this polynomial is defined as:
$$
\hat{c}*j = \sum*{i=0}^{2^{2n} - 1} c\_i \cdot \omega^{ij}, \quad \text{where } 0 \le j < 2^{2n}
$$
Here, $$\omega$$ is a primitive $$2^{2n}$$-th root of unity.
We can decompose this equation using index splitting as follows (where $$0 \le j\_0, j\_1 < 2^n$$):
$$
\begin{align\*}
\hat{c}*{j\_1 \cdot 2^n + j\_0}
&= \sum*{i\_0 = 0}^{2^n - 1} \sum\_{i\_1 = 0}^{2^n - 1} c\_{i\_1 \cdot 2^n + i\_0} \cdot \omega^{(i\_1 \cdot 2^n + i\_0)(j\_1 \cdot 2^n + j\_0)} \\
&= \underbrace{
\left(\sum\_{i\_0 = 0}^{2^n - 1}
\underbrace{\left( \omega^{i\_0 j\_0}
\underbrace{
\left(
\sum\_{i\_1 = 0}^{2^n - 1} c\_{i\_1 \cdot 2^n + i\_0} \cdot (\omega^{2^n})^{(j\_1 \cdot 2^n + j\_0)i\_1}
\right)}*{\text{Step 1}}
\right)}*{\text{Step 2}}
\cdot (\omega^{2^n})^{i\_0 j\_1}\right)}\_{\text{Step 3}}
\end{align\*}
$$
### Example ($$n=2$$)
Let $$P(X) = c\_0 + c\_1 X + \cdots + c\_{15} X^{15}$$, and suppose $$\omega^{16} = 1$$. Define the following input vectors:
$$
\begin{aligned}
\mathbf{c}^{(0)} &= (c\_0, c\_4, c\_8, c\_{12}) \\
\mathbf{c}^{(1)} &= (c\_1, c\_5, c\_9, c\_{13}) \\
\mathbf{c}^{(2)} &= (c\_2, c\_6, c\_{10}, c\_{14}) \\
\mathbf{c}^{(3)} &= (c\_3, c\_7, c\_{11}, c\_{15}) \\
\end{aligned}
$$
#### **Step 1: Perform FFT on each** $$\mathbf{c}^{(i\_0)}$$
$$
\begin{aligned}
\widehat{\mathbf{c}^{(0)}} &= (\widehat{c^{(0)}}\_0, \widehat{c^{(0)}}\_1, \widehat{c^{(0)}}\_2, \widehat{c^{(0)}}\_3) \\
\widehat{\mathbf{c}^{(1)}} &= (\widehat{c^{(1)}}\_0, \widehat{c^{(1)}}\_1, \widehat{c^{(1)}}\_2, \widehat{c^{(1)}}\_3) \\
\widehat{\mathbf{c}^{(2)}} &= (\widehat{c^{(2)}}\_0, \widehat{c^{(2)}}\_1, \widehat{c^{(2)}}\_2, \widehat{c^{(2)}}\_3) \\
\widehat{\mathbf{c}^{(3)}} &= (\widehat{c^{(3)}}\_0, \widehat{c^{(3)}}\_1, \widehat{c^{(3)}}\_2, \widehat{c^{(3)}}\_3)
\end{aligned}
$$
Each transform is defined by:
$$
\widehat{c^{(i\_0)}}*{j\_0} = \sum*{i\_1 = 0}^3 c\_{4 \cdot i\_1 + i\_0} \cdot (\omega^4)^{(4j\_1 + j\_0)i\_1}
$$
#### **Step 2: Construct** $$\mathbf{z}^{\[j\_0]}$$
$$
\begin{aligned}
\mathbf{z}^{\[0]} &= (\widehat{c^{(0)}}\_0, \widehat{c^{(1)}}\_0, \widehat{c^{(2)}}\_0, \widehat{c^{(3)}}\_0) \\
\mathbf{z}^{\[1]} &= (\widehat{c^{(0)}}\_1, \omega^1 \widehat{c^{(1)}}\_1, \omega^2 \widehat{c^{(2)}}\_1, \omega^3 \widehat{c^{(3)}}\_1) \\
\mathbf{z}^{\[2]} &= (\widehat{c^{(0)}}\_2, \omega^2 \widehat{c^{(1)}}\_2, \omega^4 \widehat{c^{(2)}}\_2, \omega^6 \widehat{c^{(3)}}\_2) \\
\mathbf{z}^{\[3]} &= (\widehat{c^{(0)}}\_3, \omega^3 \widehat{c^{(1)}}\_3, \omega^6 \widehat{c^{(2)}}\_3, \omega^9 \widehat{c^{(3)}}\_3)
\end{aligned}
$$
Each $$\mathbf{z}^{\[j\_0]}$$ can be defined generally as:
$$
\mathbf{z}^{\[j\_0]} := \left( \widehat{c^{(0)}}*{j\_0}, \omega^{j\_0} \widehat{c^{(1)}}*{j\_0}, \omega^{2j\_0} \widehat{c^{(2)}}*{j\_0}, \omega^{3j\_0} \widehat{c^{(3)}}*{j\_0} \right)
$$
#### **Step 3: Final FFT on each** $$\mathbf{z}^{\[j\_0]}$$
$$
\begin{aligned}
\widehat{\mathbf{z}^{\[0]}} &= (\hat{c}\_0, \hat{c}\_4, \hat{c}*8, \hat{c}*{12}) \\
\widehat{\mathbf{z}^{\[1]}} &= (\hat{c}\_1, \hat{c}\_5, \hat{c}*9, \hat{c}*{13}) \\
\widehat{\mathbf{z}^{\[2]}} &= (\hat{c}*2, \hat{c}*6, \hat{c}*{10}, \hat{c}*{14}) \\
\widehat{\mathbf{z}^{\[3]}} &= (\hat{c}*3, \hat{c}*7, \hat{c}*{11}, \hat{c}*{15})
\end{aligned}
$$
Each transform is again a standard FFT:
$$
\widehat{z^{\[j\_0]}}*{j\_1} = \sum*{i\_0 = 0}^3 {z^{\[j\_0]}}\_{i\_0} \cdot (\omega^4)^{i\_0 j\_1}
$$
#### **Verification Examples**
* $$\widehat{z^{\[1]}}\_2 = \hat{c}\_9$$ $$(j\_1 = 2, j\_0 = 1)$$
$$
\begin{align\*}
\widehat{z^{\[1]}}\_2 &= {z^{\[1]}}*0 + {z^{\[1]}}*1 \omega^{8} + {z^{\[1]}}*2 \omega^{16} + {z^{\[1]}}*3 \omega^{24} \\
&= \widehat{c^{(0)}}*1 + \widehat{c^{(1)}}*1 \omega^{9} + \widehat{c^{(2)}}*1 \omega^{18} + \widehat{c^{(3)}}*1 \omega^{27} \\
&= \sum*{i\_1=0}^3 c*{4i\_1} (\omega^4)^{9i\_1} + \sum*{i\_1=0}^3 c*{4i\_1 + 1} (\omega^4)^{9i\_1}\omega^9 + \sum*{i\_1=0}^3 c*{4i\_1 + 2} (\omega^4)^{9i\_1}\omega^{18} + \sum*{i\_1=0}^3 c*{4i\_1 + 3} (\omega^4)^{9i\_1}\omega^{27} \\
&= \hat{c}\_9
\end{align\*}
$$
* $$\widehat{z^{\[2]}}\_1 = \hat{c}\_6$$ $$(j\_1 = 1, j\_0 = 2)$$
$$
\begin{align\*}
\widehat{z^{\[2]}}\_1 &= {z^{\[2]}}*0 + {z^{\[2]}}*1 \omega^{4} + {z^{\[2]}}*2 \omega^{8} + {z^{\[2]}}*3 \omega^{12} \\
&= \widehat{c^{(0)}}*2 + \widehat{c^{(1)}}*2 \omega^{6} + \widehat{c^{(2)}}*2 \omega^{12} + \widehat{c^{(3)}}*2 \omega^{18} \\
&= \sum*{i\_1=0}^3 c*{4i\_1} (\omega^4)^{6i\_1} + \sum*{i\_1=0}^3 c*{4i\_1 + 1} (\omega^4)^{6i\_1} \omega^6 + \sum*{i\_1=0}^3 c*{4i\_1 + 2} (\omega^4)^{6i\_1} \omega^{12} + \sum*{i\_1=0}^3 c*{4i\_1 + 3} (\omega^4)^{6i\_1} \omega^{18} \\
&= \hat{c}\_6
\end{align\*}
$$
The inverse FFT is structurally similar, but we do not cover it in this article.
## Distributed FFT
The Parallel FFT algorithm described above can be implemented as a **Distributed FFT** by mapping it onto the MapReduce model. The diagram above illustrates how the same example from the parallel FFT is executed within the MapReduce paradigm.
* **Map phase:** Each executor performs the first-stage FFTs over $$\mathbf{c}^{(i\_0)}$$
* **Shuffle (transpose + twist):** Results are reorganized into $$\mathbf{z}^{\[j\_0]}$$
* **Reduce phase:** Second-stage FFTs are computed over each $$\mathbf{z}^{\[j\_0]}$$
This structure enables FFT computations over extremely large input sizes to be parallelized and scaled effectively in distributed systems like [Spark](https://spark.apache.org/) or [Hadoop](https://hadoop.apache.org/).
## Reference
*
> Written by [Ryan Kim](https://app.gitbook.com/u/cPk8gft4tSd0Obi6ARBfoQ16SqG2 "mention") of Fractalyze