# Applications of FFT

## Polynomial Evaluation at Roots of Unity

FFT computes evaluations of a polynomial $P(x)=a_0+a_1x + ... + a_{n-1}x^{n-1}$ at $n$-th roots of unity in one $O(n\log n)$.

- Without FFT (Naive Evaluation): it requires $n$ multiplications and additions per points. Evaluating at $n$ points results in a total cost of $O(n^2)$.

:::info
In the commit phase of [FRI](https://hackmd.io/@YaoGalteland/SJhTGtsZ1x), the prover needs to compute the polynomial evaluation over domains to generate the Merkle hash. FFT accelerates this process significantly, ensuring scalability for large polynomials.
:::

## Multiplication and Division
FFT is widely used to compute the product of two polynomials $f(x), g(x)$, significantly speeding up the process.

**Procedure**
- Run FFT on the coefficients of $f(x)$ and $g(x)$ to compute their evaluations at the $n$-th roots of unity.
- Multiply the evaluations point-wise, which corresponds to multiplying the polynomials in the frequency domain.
- Apply the Inverse FFT (iFFT) on the resulting evaluations to transform the product back to the coefficient representation.

**Cost Analysis**:
- Without FFT (Naive Evaluation) requires $O(n^2)$ operations.
- With FFT costs $O(n\log n)$ operations.

:::info
Division can apply the [RECIPROCAL](https://web.archive.org/web/20210404041913/https://web.cs.iastate.edu/%7Ecs577/handouts/polydivide.pdf) procedure. In computing the quotient, all the multiplications can be carried out by FFT.
:::
## Interpolation of Polynomials
Inverse FFT is used for interpolation, transforming evaluation points $(P(1), P(\omega), ... ,P(\omega^{n-1}))$ back to the coefficient representation of the polynomial.

**Cost Analysis**:
- Without FFT: naive interpolation involves solving a Vandermonde system, which costs $O(n^2)$.
- With FFT: the cost is $O(n\log n)$.

## Folding

Given a polynomial $P(X)$ that is evaluated over a domain $D=<\omega>$, and then folded into a smaller domain $D^d=<\omega^d>$.

$P(X)$ can be **decomposed** to
$$P(X)=F_0(X^d)+F_1(X^d)\cdot X + ... + F_{d-1}(X^d)\cdot X^{d-1}.$$
This decomposition uses the fact that $X^d$ reduces the domain size by $d$.

The new polynomial
$$P^*(X)=F_0(X)+F_1(X)\cdot \alpha + ... + F_{d-1}(X)\cdot \alpha^{d-1}$$ for some folding challenge $\alpha$, is of lower degree and is evaluated over the smaller domain $D^d$.

To understand the folding process, we define a two-virable representation:
$$q(X,Y)=F_0(Y)+F_1(Y)\cdot X + ... + F_{d-1}(Y)\cdot X^{d-1}.$$
Note that $P^*(X)=q(\alpha,X)$.

### Key Insight: Relationship Between Original and Folded Evaluations

For any $y=x^d\in D^d$, the coefficients $F_0(y),F_1(y),..., F_{d-1}(y)$ are uniquely determined by the evaluations $q(X,y)$ over the set $x\cdot U$, where $U$ is the subgroup of the $d$-th roots of unity.

#### Steps to Compute $F_0(y),F_1(y),..., F_{d-1}(y)$:
1. Define a univariate polynomial $h(X)=q(x\cdot X,y)$ over the domain $U$.
2. Note that its coefficients are related to $F_i(y)$ by the scaling factors $x^i$:
$$\text{Coefficients of }h(X)=F_0(y),F_1(y)\cdot x,..., F_{d-1}(y)\cdot x^{d-1}.$$
3. Use inverse FFT (iFFT) to interpolate $h(X)$ from its evaluations over $U$:
$$h_0,h_1,..., h_{d-1}:=iFFT(h(X)|_U)=iFFT(P(x\cdot X)|_U).$$
2. Compute $F_i(y)=\frac{h_i}{x^i}$ for $i=0,1,...,d-1.$

#### Final Relation
The relationship between the folded evaluation $P^*(y)$ and the original evaluations $P(x\cdot U)$ is expressed as:

$$
\begin{align*}
P^*(y) &= F_0(X)+F_1(X)\cdot \alpha + ... + F_{d-1}(X)\cdot \alpha^{d-1}, \\
&= h_0 + h_1 \cdot \frac{\alpha}{x} + \dots + h_{d-1} \cdot (\frac{\alpha}{x})^{d-1}\\
&=iFFT(P(x\cdot X)|_U)(\frac{\alpha}{x})
\end{align*}
$$

:::info
FFT plays a critical role in folding operations, commonly used in protocols like zk-STARKs and FRI.
:::