2 FFT

Polynomial Operations and Representation¶

约 496 个字预计阅读时间 2 分钟共被读过次

A polynomial $A(x)$ can be written in the following forms:
$$
\begin{aligned}
A(x) &= a_0 + a_1x + a_2x^2 + \cdots + a_{n-1}x^{n-1} \\
&= \sum_{k=0}^{n-1} a_k x^k \\
&= \left\langle a_0, a_1, a_2, \ldots, a_{n-1} \right\rangle \quad \text{(coefficient vector)}
\end{aligned}
$$

The degree of $A$ is $n-1$¶

Operations on Polynomials¶

Evaluation: Given $ A(x) $ and $ x_0 $, compute $ A(x_0) $.
- Horner's Rule:
$$
A(x) = a_0 + x\left(a_1 + x\left(a_2 + \cdots + x\left(a_{n-1}\right)\cdots\right)\right)
$$
Time: $ O(n) $.
Addition: $ C(x) = A(x) + B(x) $.
- $ c_k = a_k + b_k $.
Time: $ O(n) $.
Multiplication: $ C(x) = A(x) \cdot B(x) $.
- $ c_k = \sum_{j=0}^k a_j b_{k-j} $.
- Naive Time: $ O(n^2) $.
- FFT Time: $ O(n \log n) $.

Representations of Polynomials¶

Representation	Evaluation	Addition	Multiplication
Coefficients	$ O(n) $	$ O(n) $	$ O(n^2) $
Roots	$ O(n) $	Impossible	$ O(n) $
Samples	$ O(n^2) $	$ O(n) $	$ O(n) $

Key Insight: Convert between coefficients and samples in $ O(n \log n) $ time using FFT.

Divide and Conquer Algorithm for Polynomial Multiplication¶

Divide: Split $ A(x) $ into even and odd coefficients:
$$
\begin{aligned}
A_{\text{even}}(x) &= \sum_{k=0}^{\lceil n/2 \rceil -1} a_{2k} x^k, \\
A_{\text{odd}}(x) &= \sum_{k=0}^{\lfloor n/2 \rfloor -1} a_{2k+1} x^k.
\end{aligned}
$$
Conquer: Recursively compute $ A_{\text{even}}(y) $ and $ A_{\text{odd}}(y) $ for $ y \in X^2 $.
Combine:
$$
A(x) = A_{\text{even}}(x^2) + x \cdot A_{\text{odd}}(x^2)
$$

Recurrence:
$$
T(n) = 2T\left(\frac{n}{2}\right) + O(n) = O(n \log n)
$$

Roots of Unity¶

Definition: The $n$ -th roots of unity are $x$ such that $x^n = 1$. They are spaced uniformly on the unit circle in the complex plane:
$$
x_k = e^{i \tau k / n}, \quad k = 0, 1, \ldots, n - 1 \quad (\tau = 2\pi)
$$

Collapsing Property: For $n = 2^\ell$, squaring the roots reduces the problem size by half:
$$
\left(e^{i \tau k / n}\right)^2 = e^{i \tau k / (n/2)}
$$

FFT and IFFT¶

Fast Fourier Transform (FFT)¶

DFT: Convert coefficients to samples using roots of unity:

\[ A^* = V \cdot A \quad \text{where } V_{jk} = e^{i \tau jk / n} \]

Time: $O(n \log n)$

Inverse FFT (IFFT)¶

IDFT: Convert samples back to coefficients:

\[ A = \frac{1}{n} \bar{V} \cdot A^* \]

Time: $O(n \log n)$

Polynomial Multiplication via FFT¶

Steps:

Compute $A^*= \text{FFT}(A)$ and $B^* = \text{FFT}(B)$.
Multiply samples: $C^*= A^* \cdot B^*$.
Convert back: $C = \text{IFFT}(C^*)$.

Example:

Let $A(x) = 1 + 2x$ and $B(x) = 3 + 4x$.
FFT:
$A^*= [3, -1]$, $B^* = [7, -1]$.
Multiply: $C^* = [21, 1]$.
IFFT: $C(x) = 3 + 10x + 8x^2$.

Analysis:

Naive multiplication: $O(n^2) = O(4)$.
FFT - based: $O(n \log n) = O(2 \log 2)$.

Applications of FFT¶

Signal Processing: Filtering, compression (MP3), spectral analysis.
Algorithm Design: Convolution, large integer multiplication.

Representation	Evaluation	Addition	Multiplication
Coefficients	\( O(n) \)	\( O(n) \)	\( O(n^2) \)
Roots	\( O(n) \)	Impossible	\( O(n) \)
Samples	\( O(n^2) \)	\( O(n) \)	\( O(n) \)