Proofs: Rader's algorithm

RADER-FFT computes a DFT of prime length n with (3/2) L lg L + 2L multiplications and 3 L lg L + 3n − 4 additions full

This proof shows: correctness, complexity.

Statement. Let $n$ be a prime, $N = n - 1$, $L$ the least power of two with $L \ge 2N - 1$, and $R$ a commutative ring containing an element $\omega$ with $\omega^n = 1$, and an element $\rho$ with $\rho^{L} = 1$ and $\rho^{L/2} = -1$ (when $L \ge 2$), in which $L$ is a unit. (Over $\mathbb{C}$, $\omega = e^{-2\pi i/n}$ and $\rho = e^{-2\pi i/L}$; modulo a prime $P$, this needs $n \mid P - 1$ and $L \mid P - 1$.) For every $x \in R^n$, RADER-FFT returns $X$ with $X_k = \sum_{j} x_j \omega^{jk}$, using $\frac32 L \lg L + 2L$ multiplications and $3 L \lg L + 3n - 4$ additions and subtractions in $R$.

Lemma 1 (the reindexing). Let $g$ be a primitive root modulo $n$. The maps $q \mapsto g^q \bmod n$ and $p \mapsto g^{-p} \bmod n$ are bijections from $[0, N)$ onto $\{1, \ldots, n - 1\}$, and $g^{q} g^{-p} \equiv g^{(q - p) \bmod N} \pmod n$. Proof. The multiplicative group modulo the prime $n$ has order $N$ and is generated by $g$, so $g^0, \ldots, g^{N-1}$ are distinct and exhaust it; the same holds for their inverses $g^{-p}$. Since $g^N \equiv 1$ (Fermat's little theorem), exponents may be reduced modulo $N$. $\square$

Lemma 2 (the convolution). With $a_q = x_{g^q}$ and $b_m = \omega^{g^{-m}}$ (exponents of $g$ reduced modulo $n$), for each $p \in [0, N)$,

Proof. Let $k = g^{-p} \bmod n$, which is nonzero. Split $X_k = x_0 \omega^0 + \sum_{j=1}^{n-1} x_j \omega^{jk}$ and substitute $j = g^q$ by Lemma 1. Since $\omega^n = 1$, $\omega^{jk}$ depends only on $jk \bmod n$, and $jk \equiv g^q g^{-p} \equiv g^{-((p - q) \bmod N)} \pmod n$ by Lemma 1, so $\omega^{jk} = b_{(p - q) \bmod N}$. $\square$

Lemma 3 (cyclic convolution by padding). Let $\ell$ be the linear convolution of $a$ and $b$, $\ell_r = \sum_{q + m = r} a_q b_m$ for $0 \le r \le 2N - 2$. Then $(a * b)_p = \ell_p + \ell_{p + N}$ for $0 \le p < N$, with $\ell_{2N - 1} = 0$. Proof. The pairs $(q, m) \in [0, N)^2$ with $(q + m) \bmod N = p$ are those with $q + m = p$ or $q + m = p + N$, since $0 \le q + m \le 2N - 2$. $\square$

Line L4. Let $\alpha, \beta \in R^L$ be $a$ and $b$ padded with zeros. The radix-2 FFT of length $L$ with root $\rho$ computes $\hat\alpha_k = \sum_j \alpha_j \rho^{jk}$, because $\rho^{L/2} = -1$ (the proof is on the page of the iterative FFT). Then $\hat\alpha_k \hat\beta_k = \sum_{r} \gamma_r \rho^{rk}$, where $\gamma_r = \sum_{(q + m) \bmod L = r} \alpha_q \beta_m$ is the cyclic convolution of length $L$, by expanding the product and using $\rho^L = 1$. Since $\alpha_q \beta_m \ne 0$ only if $q, m < N$, and then $q + m \le 2N - 2 < L$, no index wraps around and $\gamma_r = \ell_r$ for $r \le 2N - 2$, $\gamma_r = 0$ otherwise. The inverse FFT, run with $\rho^{-1}$ (which also satisfies $(\rho^{-1})^{L/2} = -1$) and multiplied by $L^{-1}$, returns $\gamma$: indeed $\sum_k \hat\gamma_k \rho^{-kr} = \sum_s \gamma_s \sum_k \rho^{k(s - r)} = L \gamma_r$, because for $s \ne r$ in $[0, L)$ the inner sum $S = \sum_{k<L} \rho^{kt}$, $t = (s - r) \bmod L \in (0, L)$, vanishes. To see this, write $t = 2^e d$ with $d$ odd, so $2^{e+1} \le L$, and let $K = L / 2^{e+1}$. Then $\rho^{Kt} = (\rho^{L/2})^d = -1$. Since $\rho^L = 1$, the term $\rho^{kt}$ depends only on $k \bmod L$, and $k \mapsto k + K$ permutes the residues modulo $L$, so $S = \rho^{Kt} S = -S$. Thus $2S = 0$, and $S = 0$ because $2$ divides the unit $L$ and is therefore a unit. Folding by Lemma 3 gives $c = a * b$.

Correctness. Line L5 sets $X_0 = \sum_j x_j \omega^0$. By Lemma 1, the loop at lines L6 and L7 writes each nonzero index $k = g^{-p}$ exactly once, with the value $x_0 + c_p$, which is $X_k$ by Lemma 2 and line L4. So the returned vector is $X$.

Inverse. With $\omega^{-1}$, which also has $(\omega^{-1})^n = 1$, the same program computes $\sum_k X_k \omega^{-jk}$; if $\omega$ is a principal $n$-th root of unity and $n$ is a unit, this is $n x_j$, and the final division returns $x$.

Operation count. The three FFTs of length $L$ (of $\alpha$, of $\beta$, and the inverse) each consist of $\lg L$ stages of $L/2$ butterflies, one multiplication and two additions each: $\frac{L}{2} \lg L$ multiplications and $L \lg L$ additions per FFT. The pointwise product is $L$ multiplications, and the scaling by $L^{-1}$ is $L$ more. The folding adds $\ell_{p+N}$ for $0 \le p \le N - 2$: $N - 1$ additions. Line L5 is $n - 1$ additions and line L7 is $N$ additions. The totals are $\frac32 L \lg L + 2L$ multiplications and $3 L \lg L + (N - 1) + (n - 1) + N = 3 L \lg L + 3n - 4$ additions. Since $2n - 3 \le L < 2(2n - 3)$, both are $\Theta(n \log n)$ for $n \ge 3$. The arrays have length $L$, so the extra space is $\Theta(n)$. $\blacksquare$