DFT on arbitrary rings

2019-01-12 本文已影响0人 zjsdut

摘抄自 Fast multiplication of polynomials over arbitrary rings, David G. Cantor & Erich Kaltofen

Rings with a Fourier Transform

The main feature of our algorithm is that it works over an arbitrary ring $R$ . We write $0\in R$ for its additive zero element and $1\in R$ for its multiplicative unit, $0 \ne 1$ . Any ring is $\mathbb Z$ module by $(-1) a := -a$ and $na := \sum_{j=1}^{n} a, n \in \mathbb Z, n \ge 0$ . The integers $\mathbb Z$ are embeded into $R$ by $\Pi(n) = n \cdot 1$ , and we write $n$ shortly for the element $n \cdot 1$ . Notice that a 'rng' $R$ without a unit can be embedded into the ring $\mathbb Z\times R$ with unit $(1,0)$ and addition and multiplication defined as
$(m, a) + (n, b) := (m + n, a + b), (m, a)(n, b) := (mn, mb + na + ab),$ so all our results hold for such rngs as well. The subring $\Pi(\mathbb Z)$ is either isomorphic to $\mathbb Z$ or to $\mathbb Z_m$ , the integers modulo $m$ for some $m$ . We write $R^n$ for the left $R$ -module of $n$ -dimensional vectors over $R$ , and we write $a_i, 0\le i\le n-1$ , for the $i$ -th component of ${\bf a}\in R^n$ .

In the following, we introduce the theory for the fast Fourier transform, here for the abstract module $R^n$ .

Definition: Let $R$ be a ring, $n \in \mathbb Z, n\ge 2, \omega \in R$ . Then $\omega$ is a principal $n$ -th root of unity if
(PR1) $\omega^n = 1$ ; note that then $\omega^{-1} = \omega^{n-1}$ .
(PR2) For all $i \in \mathbb Z$ : $i \not\equiv 0 \pmod{n} \implies \sum_{j = 0}^{n-1} \omega ^{ij} = 0$ .
(PR3) For all $w \in R$ : $\omega w = w \omega$ ; this condition is needed when computing convolutions in noncommutative rings.

Definition: Let $R$ be a ring, $n \ge 1$ , $\omega$ a principal $n$ -th root of unity in $R$ , ${\bf a}, \hat{\bf a} \in R^n$ . Then $\hat{\bf a}$ is the discrete Fourier transform of ${\bf a}$ with respect to $\omega$ , denoted as $\hat{\bf a} = \mathrm{DFT}[[\omega]]({\bf a})$ , respectively $\bf{a}$ is the discrete Fourier inverse of $\hat{\bf a}$ with respect to $\omega$ , ${\bf a} = \mathrm{DFI}[[\omega]](\hat{\bf a})$ , if $\text{for all $i$ with $0\le i\le n-1$: } \hat a_i = \sum_{j = 0}^{n-1} \omega^{ij} a_j.$
For the purpose of fast computation, one chooses $n = s^k$ . Following is the now-famous algorithm to compute the forward transform.

Algorithm Fast DFT
Input: $n = s^k$ , $\omega \in R$ such that $\omega^n =1$ , ${\bf a} \in R^n$ .
Output: $\hat{\bf a}=\mathrm{DFT}[[\omega]]({\bf a}) \in R^n$ .
If $n = 1$ Then Return $\hat{\bf a} \gets {\bf a} = [a_0]$ .
Step S (Split-up): Since for $0 \le i < n/s, r\in \mathbb Z_s$ we have
$\hat a_{si+r} = \sum_{j = 0}^{n-1} \omega^{(si+r)j}a_j = \sum_{j = 0}^{n/s-1}\sum_{l=0}^{s-1}\omega^{(si+r)(j+\ell n/s)} a_{j + \ell n / s} = \sum_{j = 0} ^{n/s-1} (\omega^s)^{ij} \left(\sum_{\ell = 0}^{s-1} \omega^{r\ell n/s + rj} a_{j + \ell n / s}\right)$
We have
$[\hat a_{si+r}]_{i = 0, \dots, n/s-1} = \mathrm{DFT}[[\omega^s]] \left(\left[\omega^{rj} \sum_{\ell = 0}^{s-1} \omega^{r\ell n/s} a_{j + \ell n / s}\right]\right)$

$\rho \gets \omega^{n/s}$ ; $\rho^{(0)} \gets 1$ ; $\omega^{(0)} \gets 1$ .
For $r \gets 0, \dots, s - 1$ Do
$\quad \rho^{(r)} \gets \rho^{(r-1)}$ ; $\omega^{(r)} \gets \omega^{(r-1)} \omega$ .
$\quad$ For $j \gets 0, \dots, n/s -1$ Do
$\qquad \quad \omega^{(rj)} \gets \omega^{(rj - r)} \omega^{(r)}.$
$\qquad \quad u_{j}^{(r)} \gets \omega^{(rj)} \sum_{\ell = 0}^{s-1} (\rho^{(r)})^{\ell} a_{j + \ell n /s}.$

Step R (Recursion}:
For $r \gets 0, \dots, s-1$ Do
$\quad$ Call the algorithm recursively with $n' \gets n/s, \omega' \gets \omega^s$ ,
$\quad$ and ${\bf u}^{(r)} \in R^{n/s}$ , obtaining $\hat {\bf u}^{(r)} = \mathrm{DFT}[[\omega']]({\bf u}^{(r)})$

Step I (Insertion):
For $r \gets 0, \dots, s-1$ Do
$\quad$ For $i \gets 0, \dots, n/s$ Do
$\qquad \quad \hat a_{si+r} \gets \hat u_i^{(r)}$
Return $\hat {\bf a}.\quad \square$

DFT on arbitrary rings

Rings with a Fourier Transform

猜你喜欢

热点阅读