Editing Prime-factor FFT algorithm (section)

== Algorithm ==
Let <math>a(x)</math> be a polynomial and <math>\omega_n</math> be a [[Principal root of unity|principal <math>n</math>-th root of unity]]. We define the DFT of <math>a(x)</math> as the <math>n</math>-tuple <math>(\hat{a}_j) = (a(\omega_n^j)) </math>.
In other words,
<math display="block">\hat{a}_j = \sum_{i=0}^{n-1} a_i \omega_n^{ij} \quad \text{ for all } j = 0, 1, \dots, n - 1.</math>

For simplicity, we denote the transformation as <math>\text{DFT}_{\omega_n}</math>.

The PFA relies on a coprime factorization of <math display="inline">n = \prod_{d = 0}^{D - 1} n_d</math> and turns <math>\text{DFT}_{\omega_n}</math> into <math display="inline">\bigotimes_d \text{DFT}_{\omega_{n_d}}</math> for some choices of <math>\omega_{n_d}</math>'s where <math display="inline">\bigotimes</math> is the [[tensor product]].

=== Mapping based on CRT ===

For a coprime factorization {{tmath|1= \textstyle n = \prod_{d = 0}^{D - 1} n_d }}, we have the [[Chinese remainder theorem|Chinese remainder map]] <math>m \mapsto (m \bmod n_d)</math> from <math>\mathbb{Z}_{n}</math> to <math display="inline">\prod_{d = 0}^{D - 1} \mathbb{Z}_{n_d} </math> with <math display="inline">(m_d) \mapsto \sum_{d = 0}^{D - 1} e_d m_d</math> as its inverse where {{tmath|1= e_d }}'s are the [[central idempotent|central orthogonal idempotent elements]] with <math display="inline">\sum_{d = 0}^{D - 1} e_d = 1 \pmod{n}</math>.
Choosing <math>\omega_{n_d} = \omega_n^{e_d}</math> (therefore, {{tmath|1= \prod_{d = 0}^{D - 1} \omega_{n_d} = \omega_n^{\sum_{d = 0}^{D - 1} e_d} = \omega_n }}), we rewrite <math>\text{DFT}_{\omega_n}</math> as follows:

<math display="block">\hat{a}_j = 
\sum_{i = 0}^{n - 1} a_i \omega_n^{ij} = 
\sum_{i = 0}^{n - 1} a_i \left( \prod_{d = 0}^{D - 1} \omega_{n_d} \right)^{ij} = 
\sum_{i = 0}^{n - 1} a_i \prod_{d = 0}^{D - 1} \omega_{n_d}^{ (i \bmod n_d) (j \bmod n_d)} = 
\sum_{i_0 = 0}^{n_0 - 1} \cdots \sum_{i_{D - 1} = 0}^{n_{D - 1} - 1} a_{\sum_{d = 0}^{D - 1} e_d i_d} \prod_{d = 0}^{D - 1} \omega_{n_d}^{i_d (j \bmod n_d)} .</math>

Finally, define <math>a_{i_0, \dots, i_{D - 1}} = a_{\sum_{d = 0}^{D - 1} i_d e_d}</math> and {{tmath|1= \hat{a}_{j_0, \dots, j_{D - 1} } = \hat{a}_{\sum_{d = 0}^{D - 1} j_d e_d} }}, 
we have

<math display="block">\hat{a}_{j_0, \dots, j_{D - 1}} = \sum_{i_0 = 0}^{n_0 - 1} \cdots \sum_{i_{D - 1}=0}^{n_{D - 1} - 1} a_{i_0, \dots, i_{D - 1}} \prod_{d = 0}^{D - 1} \omega_{n_d}^{i_d j_d} .</math>

Therefore, we have the multi-dimensional DFT, {{tmath|1= \textstyle \otimes_{d = 0}^{D - 1} \text{DFT}_{\omega_{n_d} } }}.

=== As algebra isomorphisms ===
PFA can be stated in a high-level way in terms of [[Algebra homomorphism|algebra isomorphisms]].
We first recall that for a commutative ring <math>R</math> and a [[group isomorphism]] from <math>G</math> to {{tmath|1= \textstyle \prod_d G_d }}, we have the following algebra isomorphism

<math display="block">R[G] \cong \bigotimes_d R[G_d] ,</math>

where <math>\bigotimes</math> refers to the [[tensor product of algebras]].

To see how PFA works, we choose <math>G = (\Z_n, +, 0)</math> and <math>G_d = (\Z_{n_d}, +, 0)</math> be [[additive group]]s.
We also identify <math>R[G]</math> as <math display="inline">\frac{R[x]}{\langle x^n - 1 \rangle}</math> and <math>R[G_d]</math> as {{tmath|1= \textstyle \frac{R[x_d]}{\langle x_d^{n_d} - 1 \rangle} }}.
Choosing <math>\eta = a \mapsto (a \bmod n_d)</math> as the group isomorphism {{tmath|1= \textstyle G \cong \prod_d G_d }}, we have the algebra isomorphism <math display="inline">\eta^* : R[G] \cong \bigotimes_d R[G_d]</math>, or alternatively,

<math display="block"> \eta^* : \frac{R[x]}{\langle x^n - 1 \rangle} \cong \bigotimes_d \frac{R[x_d]}{\langle x_d^{n_d} - 1 \rangle} .</math>

Now observe that <math>\text{DFT}_{\omega_n}</math> is actually an algebra isomorphism from <math display="inline">\frac{R[x]}{\langle x^n - 1 \rangle}</math> to <math display="inline">\prod_i \frac{R[x]}{\langle x - \omega_n^i \rangle}</math> and each <math>\text{DFT}_{\omega_{n_d}}</math> is an algebra isomorphism from <math display="inline">\frac{R[x]}{\langle {x_d}^{n_d} - 1 \rangle}</math> to <math display="inline">\prod_{i_d} \frac{R[x_d]}{\langle x_d - \omega_{n_d}^{i_d} \rangle}</math>,
we have an algebra isomorphism <math>\eta'</math> from <math display="inline">\bigotimes_d \prod_{i_d} \frac{R[x_d]}{\langle x_d - \omega_{n_d}^{i_d} \rangle}</math> to <math display="inline">\prod_i \frac{R[x]}{\langle x - \omega_n^i \rangle}</math>.
What PFA tells us is that <math display="inline">\text{DFT}_{\omega_n} = \eta' \circ \bigotimes_d \text{DFT}_{\omega_{n_d}} \circ \eta^*</math> where <math>\eta^*</math> and <math>\eta'</math> are re-indexing without actual arithmetic in <math>R</math>.

=== Counting the number of multi-dimensional transformations ===
Notice that the condition for transforming <math>\text{DFT}_{\omega_n}</math> into <math display="inline">\eta' \circ \bigotimes_d \text{DFT}_{\omega_{n_d}} \circ \eta^*</math> relies on "an" additive group isomorphism <math>\eta</math> from <math>(\mathbb{Z}_n, +, 0)</math> to {{tmath|1= \textstyle \prod_d (\Z_{n_d}, +, 0) }}.
Any additive group isomorphism will work.
To count the number of ways transforming <math>\text{DFT}_{\omega_n}</math> into {{tmath|1= \textstyle \eta' \circ \bigotimes_d \text{DFT}_{\omega_{n_d} } \circ \eta^* }},
we only need to count the number of additive group isomorphisms from <math>(\mathbb{Z}_n, +, 0)</math> to <math display="inline">\prod_d (\mathbb{Z}_{n_d}, +, 0)</math>, or alternative, the number of additive group [[automorphism]]s on {{tmath|1= (\Z_n, +, 0) }}.
Since <math>(\mathbb{Z}_n, +, 0)</math> is [[Cyclic group|cyclic]], any automorphism can be written as <math>1 \mapsto g</math> where <math>g</math> is a [[Cyclic group|generator]] of <math>(\mathbb{Z}_n, +, 0)</math>.
By the definition of {{tmath|1= (\Z_n, +, 0) }}, <math>g</math>'s are exactly those coprime to <math>n</math>.
Therefore, there are exactly <math>\varphi(n)</math> many such maps where <math>\varphi</math> is the [[Euler's totient function]].
The smallest example is <math>n = 6</math> where <math>\varphi(n) = 2</math>, demonstrating the two maps in the literature: the "CRT mapping" and the "Ruritanian mapping".<ref>{{harvnb|Good|1971}}</ref>