# 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](mailto:undefined) of Fractalyze
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://fractalyze.gitbook.io/intro/primitives/number-theoretic-transform/parallel-distributed-fft.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.