Proofs: Real-valued FFT

REAL-FFT returns X_0, …, X_(n/2) of a real sequence with n lg n + 3n + 8 real multiplications and (3/2) n lg n + (5/2) n + 8 real additions full

This proof shows: correctness, complexity.

Setting. Let $K$ be $\mathbb{C}$ with complex conjugation, or $\mathbb{Z}_p[i] = \mathbb{Z}_p[t]/(t^2 + 1)$ for an odd prime $p$ with $\overline{a + bi} = a - bi$. In both cases conjugation is a ring automorphism of order at most $2$ that fixes the subring $F$ of "real" elements ($\mathbb{R}$ or $\mathbb{Z}_p$) and sends $i$ to $-i$, and $2$ and $i$ are units. Let $n = 2h$ with $h = 2^{s}$, $s \ge 0$, and let $\omega \in K$ satisfy $\omega^n = 1$, $\omega^h = -1$ and $\omega \bar\omega = 1$. Over $\mathbb{C}$, $\omega = e^{-2\pi i/n}$ satisfies all three.

Statement. For every $x \in F^n$, REAL-FFT returns $X_0, \ldots, X_h$, where $X_k = \sum_{j=0}^{n-1} x_j \omega^{jk}$, and moreover $X_{n-k} = \overline{X_k}$ for all $k$. If moreover $\omega^k - 1$ is a unit for $0 < k < n$ (true over $\mathbb{C}$, in the field $\mathbb{Z}_p[i]$ for $p \equiv 3 \pmod 4$, and for the roots used in the tests when $p \equiv 1 \pmod 4$, whose images in $\mathbb{Z}_p \times \mathbb{Z}_p$ are $(a^k - 1, a^{-k} - 1)$ with $a$ of order $n$), the inverse procedure of the page returns $x$ from $X_0, \ldots, X_h$. Counting a multiplication in $K$ as $4$ multiplications and $2$ additions in $F$, and an addition in $K$ as $2$ additions in $F$, REAL-FFT does $n \lg n + 3n + 8$ multiplications and $\frac32 n \lg n + \frac52 n + 8$ additions in $F$.

Conjugation of a transform. For $y \in F^m$ and $\nu \in K$ with $\nu^m = 1$ and $\nu \bar\nu = 1$, write $Y_k = \sum_{j<m} y_j \nu^{jk}$. Then $\bar\nu = \nu^{-1}$, so $\overline{Y_k} = \sum_j y_j \nu^{-jk} = \sum_j y_j \nu^{j(m-k)} = Y_{m-k}$, using $\bar y_j = y_j$ and $\nu^{jm} = 1$. Applied to $x$ and $\omega$ this gives $X_{n-k} = \overline{X_k}$. $\quad (1)$

The pieces. Let $\nu = \omega^2$, so $\nu^h = 1$ and $\nu \bar\nu = 1$, and let $e_j = x_{2j}$, $o_j = x_{2j+1}$ for $0 \le j < h$, with transforms $E_k = \sum_j e_j \nu^{jk}$ and $O_k = \sum_j o_j \nu^{jk}$, defined for all integers $k$ and of period $h$. Splitting the sum for $X_k$ by the parity of the index,

Lines L2 to L4. Line L2 sets $z_j = e_j + i o_j$. Line L3 computes $Z_k = \sum_j z_j \nu^{jk}$ for $0 \le k < h$: the radix-2 FFT of length $h$ with root $\nu$ is correct when $\nu^{h/2} = -1$ for $h \ge 2$, which holds since $\nu^{h/2} = \omega^h = -1$ (see the iterative FFT page for its proof). By linearity, $Z_k = E_k + i O_k$. Line L4 extends $Z$ by period $h$, which is consistent since $\nu^{jh} = 1$.

Lines L6 and L7. By (1) for $e$ and $o$ with root $\nu$, $\overline{E_{h-k}} = E_k$ and $\overline{O_{h-k}} = O_k$. Hence $\overline{Z_{h-k}} = \overline{E_{h-k}} + \bar i\, \overline{O_{h-k}} = E_k - i O_k$. So $Z_k + \overline{Z_{h-k}} = 2 E_k$ and $Z_k - \overline{Z_{h-k}} = 2i O_k$, and since $2$ and $i$ are units, lines L6 and L7 set $E = E_k$ and $O = O_k$, for each $0 \le k \le h$.

Line L8. By (2), $E + \omega^k O = X_k$. So the returned list is $(X_0, \ldots, X_h)$. For $n = 1$ the procedure returns $x_0 = X_0$ directly.

Inverse. Given $X_0, \ldots, X_h$ of a real $x$, (1) gives $X_{k+h} = \overline{X_{h-k}}$ for $0 \le k < h$. By (2) and the period $h$ of $E, O$, $X_k = E_k + \omega^k O_k$ and $X_{k+h} = E_k + \omega^{k+h} O_k = E_k - \omega^k O_k$. So $\frac12(X_k + \overline{X_{h-k}}) = E_k$ and $\frac12 (X_k - \overline{X_{h-k}}) \omega^{-k} = O_k$, and the procedure forms $Z_k = E_k + i O_k$, which is the transform of $z = e + i o$ with root $\nu$. The inverse transform of length $h$, with $\nu^{-1}$ and the factor $1/h$, returns $z$: for $0 < k < h$, $\nu^k - 1 = \omega^{2k} - 1$ is a unit by hypothesis, so $\sum_{j<h} \nu^{jk} = (\nu^{kh} - 1)/(\nu^k - 1) = 0$, which is the orthogonality the inverse needs, and $h$ is a unit because $2$ is. Writing $z_j = e_j + i o_j$ with $e_j, o_j \in F$, the real and imaginary parts give $x_{2j} = e_j$ and $x_{2j+1} = o_j$, because $F \oplus F i = K$ is a direct sum.

Operation count. The radix-2 FFT of length $h = 2^s$ does $\frac{h}{2} s$ multiplications and $h s$ additions in $K$, one multiplication and two additions for each of the $\frac h2$ butterflies of each of the $s$ stages. With $s = \lg n - 1$ and $h = n/2$, this is $\frac{n}{4}(\lg n - 1)$ multiplications and $\frac n2 (\lg n - 1)$ additions in $K$, so $n (\lg n - 1)$ multiplications and $\frac n2 (\lg n - 1) + n (\lg n - 1) = \frac32 n (\lg n - 1)$ additions in $F$. Each of the $h + 1$ iterations of lines L5 to L8 does: at L6, one addition in $K$ ($2$ in $F$) and a scaling by $\frac12$ ($2$ multiplications in $F$); at L7, one addition in $K$ ($2$) and a scaling by $\frac{1}{2i} = -\frac{i}{2}$, which maps $a + bi$ to $\frac b2 - \frac a2 i$ ($2$ multiplications); at L8, one multiplication in $K$ ($4$ multiplications and $2$ additions) and one addition in $K$ ($2$). That is $8$ multiplications and $8$ additions in $F$ per iteration, $4n + 8$ of each in total, since $h + 1 = \frac n2 + 1$. Conjugation is a sign change and is not counted. Adding up, the multiplications number $n(\lg n - 1) + 4n + 8 = n \lg n + 3n + 8$ and the additions $\frac32 n(\lg n - 1) + 4n + 8 = \frac32 n \lg n + \frac52 n + 8$. $\blacksquare$