Towards an iterative algorithm for the DTF

We first change the intermediate polynomials. Let $n=2^r$ be a power of $2$ , let ${\omega} \in R$ be a primitive $n$ -th root of unity and $A(x) = {\Sigma}_{0 \, \leq \, i \, < \, n} \ a_i \, x^i$ . We define

$$\begin{array}{rcl} A^{[0]}(x) & = & a_0 + a_2 x + a_4 x^2 + \... ... + a_3 x + a_5 x^2 + \cdots + a_{n-1} x^{n/2 -1} \\ \end{array}$$ (55)

such that we have

$$A(x) \ = \ A^{[0]}(x^2) + x \, A^{[1]}(x^2).$$ (56)

Hence evaluating $A$ at $1, {\omega}, {\omega}^2, \ldots, {\omega}^{n-1}$ is reduced to evaluate $A^{[0]}$ and $A^{[1]}$ at $1, {\omega}^2, {\omega}^4, \ldots, {\omega}^{2n-2}$ . But this second sequence of powers of ${\omega}$ consists of two identical sequences of length $n/2$ . Indeed, for every integer $k$ we have

$$({\omega}^{k+ n/2})^2 \ = \ ({\omega}^{k})^2$$ (57)

Since ${\omega}^{k} (1 - {\omega}^{n/2}) \neq 0$ holds, we obtain

$${\omega}^{k+ n/2} \ = \ - {\omega}^{k}$$ (58)

Hence we only need to evaluate $A^{[0]}$ and $A^{[1]}$ at

$$1, {\omega}^2, {\omega}^4, \ldots, {\omega}^{n-2}.$$ (59)

This provides us directly with the values of $A$ at

$$1, {\omega}, {\omega}^2, \ldots, {\omega}^{n/2-1}$$ (60)

and the values of $A$ at

$${\omega}^{n/2}, {\omega}^{n/2+1}, \ldots, {\omega}^{n-1}$$ (61)

by using the fact these numbers are respectively equal to

$$-1, -{\omega}, -{\omega}^2, \ldots, -{\omega}^{n/2-1}.$$ (62)

To summarize, for $0 \leq i \leq n/2 -1$ we have

$$\begin{array}{rcl} A({\omega}^i) & = & A^{[0]}({\omega}^{2i})... ...ga}^{2i}) - {\omega}^i \, A^{[1]}({\omega}^{2i}) \\ \end{array}$$ (63)

Algorithm 3  

The validity of Algorithm 3 follows from the two following observations.

• Formulas (63).
• If ${\omega}$ is a primitive $2^s$ -root of unity, with $s > 1$ , then ${\omega}^2$ is a primitive $2^{s-1}$ -root of unity.

Observe that the recursive calls of $DFT(n,A,{\Omega})$ defines an ordering of the coefficients of $A$ shown on Figure 2 for $n=8$ . Let us call this ordering the DFT ordering of $A$ .

Observe that if the input array $A$ is sorted w.r.t. this DFT ordering, one can describe easily the recursive calls with a binary tree. If this tree is traversed bottom-up, from left to right, we are led to an iterative algorithm working in place! For instance, for $n=8$ , assuming that the input array $A$ is

$$\mid a_0 \mid a_4 \mid a_2 \mid a_6 \mid a_1 \mid a_5 \mid a_3 \mid a_7 \mid$$

We obtain the desired result in $A$ using the following straigth-line program

1. $a$ := $a_0$
2. $b$ := $a_1$
3. $a_0$ := $a + b$
4. $a_1$ := $a - b$
5. $a$ := $a_2$
6. $b$ := $a_3$
7. $a_2$ := $a + b$
8. $a_3$ := $a - b$
9. $a$ := $a_4$
10. $b$ := $a_5$
11. $a_4$ := $a + b$
12. $a_5$ := $a - b$
13. $a$ := $a_6$
14. $b$ := $a_7$
15. $a_6$ := $a + b$
16. $a_7$ := $a - b$
17. $a$ := $a_0$
18. $b$ := $a_1$
19. $c$ := $a_2$
20. $d$ := $a_3$
21. $a_0$ := $a + c$
22. $a_2$ := $a - c$
23. $a_1$ := $b + {\omega} d$
24. $a_3$ := $b - {\omega} d$
25. $a$ := $a_4$
26. $b$ := $a_5$
27. $c$ := $a_6$
28. $d$ := $a_7$
29. $a_0$ := $a + c$
30. $a_2$ := $a - c$
31. $a_1$ := $b + {\omega} d$
32. $a_3$ := $b - {\omega} d$
33. $a$ := $a_0$
34. $b$ := $a_1$
35. $c$ := $a_2$
36. $d$ := $a_3$
37. $e$ := $a_4$
38. $f$ := $a_5$
39. $g$ := $a_6$
40. $h$ := $a_7$
41. $a_0$ := $a + e$
42. $a_1$ := $b + {\omega} f$
43. $a_2$ := $c + {\omega}^2 f$
44. $a_3$ := $d + {\omega}^3 h$
45. $a_4$ := $a + e$
46. $a_5$ := $b - {\omega} f$
47. $a_6$ := $c - {\omega}^2 f$
48. $a_7$ := $d - {\omega}^3 h$

Figure 2: Recursive calls for $n=8$ .

Algorithm 4  

Remark 8   To get the DFT ordering for $A$ , that is $[a_0, a_4, a_2, a_6, a_1, a_5, a_3, a_7]$ , observe that this ordering changes

$$000, 001, 010, 011, 100, 101, 011, 111$$ (64)

to

$$000, 100, 010, 110, 001, 101, 110, 111$$ (65)

Remark 9   The ring ${\mbox{${\mathbb{Z}}$}}$ does not have any interesting roots of unity. In order to take advantage of the FFT-based multiplication one could use a modular approach as follows.

• Let $f$ and $g$ be two univariate polynomials in ${\mbox{${\mathbb{Z}}$}}[x]$ . We can assume that all their coefficients are positive. Otherwise, we can restrict to this case by setting

  $$f \ = \ f^+ - f^{-} \ \ \ \ {\rm and} \ \ \ \ g \ = \ g^+ - g^{-}$$ (66)

  
  
  where $f^+$ , $f^{-}$ , $g^+$ , $g^{-}$ are polynomials with positive coefficients and writing

  $$f \, g \ = \ f^+ g^+ + f^{-} g^{-} - f^+ g^{-} - f^{-} g^+$$ (67)

  
  
  and computing the products $f^+ g^+$ , $f^{-} g^{-}$ , $f^+ g^{-}$ and $f^{-} g^+$ one after another.
• Let ${\mid}{\mid}f{\mid}{\mid}$ and ${\mid}{\mid}g{\mid}{\mid}$ be the max-norms of $f$ and $g$ . Let $d$ be the degree of $f \, g$ . For $k = 0 \cdots d$ a bound for the coefficient $c_k$ of $x^k$ in $f \, g$ is given by

  $${\mid} c_k {\mid} \ \leq \ (k+1) {\mid}{\mid}f{\mid}{\mid} {\mid}{\mid}g{\mid}{\mid}$$ (68)

  
  

• Let $M$ be the biggest value of these bounds. Let $p_1, \ldots, p_r$ be primes such
  • $2^d$ divides each $p_1 -1, \ldots, p_r - 1$
  • the product of $p_1, \ldots, p_r$ is bigger than $2 \, M$ .
• Then we can compute $f \, g$ in each of the ${\mbox{${\mathbb{Z}}$}}/p_i{\mbox{${\mathbb{Z}}$}}[x]$ using the FFT-based multiplication.
• Finally we can recombine these modular product by applying the CRA to each coefficient $c_k$ (of $x^k$ ) in $f \, g$ .