The Fast Fourier Transform

The Fast Fourier Transform computes the DFT quickly. This important algorithm for computer science (not only computer algebra, but also digital signal processing for instance) was (re)-discovered in 1965 by Cooley and Tukey.

Let $n$ be a positive even integer, ${\omega} \in R$ be a primitive $n$ -th root of unity and $f = {\Sigma}_{0 \, \leq \, i \, < \, n} \ f_i \, x^i$ . In order to evaluate $f$ at $1, {\omega}, {\omega}^2, \ldots, {\omega}^{n-1}$ , we follow a divide-and-conquer strategy; more precisely, we consider the divisions with remainder of $f$ by $x^{n/2} -1$ and $x^{n/2} +1$ . So let $q_0, q_1, r_0, r_1$ be polynomials such that

$$f \ = \ q_0 (x^{n/2} -1) + r_0 \ \ \ \ {\rm with} \ \ \ \ \left\{ \begin{array}{cc} {\deg}(r_0) < n/2 \\ {\deg}(q_0) < n/2 \end{array} \right.$$ (31)

and

$$f \ = \ q_1 (x^{n/2} +1) + r_1 \ \ \ \ {\rm with} \ \ \ \ \left\{ \begin{array}{cc} {\deg}(r_1) < n/2 \\ {\deg}(q_1) < n/2 \end{array} \right.$$ (32)

The relations ${\deg}(q_0) < n/2$ and ${\deg}(q_1) < n/2$ hold because the polynomial $f$ has degree less than $n$ . Observe that the computation of $(q_0, r_0)$ and $(q_1, r_1)$ can be done very easily. Indeed, let $F_0, F_1 \in R[x]$ be such that

$$f \ = \ F_1 \, x^{n/2} + F_0 \ \ \ \ {\rm with} \ \ \ \ \left\{ \begin{array}{cc} {\deg}(F_1) < n/2 \\ {\deg}(F_0) < n/2 \end{array} \right.$$ (33)

We have

$$f \ = \ F_1 (x^{n/2} - 1) + F_0 + F_1 \ \ \ \ {\rm and} \ \ \ \ f \ = \ F_1 (x^{n/2} + 1) + F_0 - F_1$$ (34)

Hence we obtain

$$r_0 \ = \ F_0 + F_1 \ \ \ \ {\rm and} \ \ \ \ r_1 \ = \ F_0 - F_1$$ (35)

Let $i$ be an integer such that $0 \leq i < n/2$ . By using Relation (31) with $x = {\omega}^{2 \, i}$ we obtain

$$f({\omega}^{2 \, i}) \ = \ q_0({\omega}^{2 \, i}) ({\omega}^{n \, i} - 1) + r_0({\omega}^{2 \, i}) \ = \ r_0({\omega}^{2 \, i})$$ (36)

since ${\omega}^{n \, i} = 1$ . Then, by using Relation (32) with $x = {\omega}^{2 \, i + 1}$ we obtain

$$f({\omega}^{2 \, i + 1}) \ = \ q_1({\omega}^{2 \, i + 1}) ({\omeg... ...omega}^{n/2} + 1) + r_1({\omega}^{2 \, i + 1}) \ = \ r_1({\omega}^{2 \, i + 1})$$ (37)

since ${\omega}^{n/2} = -1$ . Indeed, this last equation follows from

$$0 \ = \ {\omega}^{n} - 1 \ = \ ({\omega}^{n/2} - 1) ({\omega}^{n/2} + 1)$$ (38)

and the fact that ${\omega}^{n/2} - 1$ is not zero nor a zero divisor. Therefore we have proved the following

Proposition 4   Evaluating $f \in R[x]$ (with degree less than $n$ ) at $1, {\omega}^1, \ldots, {\omega}^{n-1}$ is equivalent to

• evaluate $r_0$ at the even powers ${\omega}^{2 \, i}$ for $0 \leq i < n/2$ , and
• evaluate $r_1$ at the odd powers ${\omega}^{2 \, i + 1}$ for $0 \leq i < n/2$ .

Since it is easy to show that ${\omega}^2$ is a primitive $n/2$ -th root of unity we can hope for a recursive algorithm. This algorithm would be easier if both $r_0$ and $r_1$ would be evaluated at the same points. So we define

$$\ {r_1}^{\ast}({\omega}^{2 \, i}) = r_1({\omega}^{2 \, i + 1}).$$ (39)

Now we obtain the following algorithm.

Algorithm 1  

Theorem 1   Let $n$ be a power of $2$ and ${\omega} \in R$ be a primitive $n$ -th root of unity. Then Algorithm 1 computes $DTF_{\omega}(f)$ using

• $n \, {\log}(n)$ additions in $R$ ,
• $(n/2) \, {\log}(n)$ multiplications by powers of ${\omega}$ .

leading in total to $3/2 \, n \, {\log}(n)$ ring operations.

Proof. By induction on $k = {\log}_2(n)$ . Let $S(n)$ and $T(n)$ be the number of additions and multiplications in $R$ that the algorithms requires for an input of size $n$ . If $k = 0$ the algorithm returns $(f_0)$ whose costs is null thus we have $S(0) = 0$ and $T(0) = 0$ which satisfies the formula since ${\log}(n) = {\log}(1) = 0$ . Assume $k > 0$ . Just by looking at the algorithm we that

$$S(n) \ = \ 2 \, S(n/2) + n \ \ \ \ {\rm and} \ \ \ \ T(n) \ = \ 2 \, T(n/2) + n/2$$ (40)

leading to the result by plugging in the induction hypothesis. $\qedsymbol$