0.1 Preliminaries  (Page 4/5)

First, consider $n=p$ , a prime. Let

and recall $s^p-1=(s-1)(s^{p-1}+s^{p-2}+\cdots +s+1)={\Phi }_1\left(s\right){\Phi }_p\left(s\right)$ . The residue $⟨X\left(s\right){⟩}_{{\Phi }_1\left(s\right)}$ is found by summing the coefficients of $X\left(s\right)$ .The residue $⟨X\left(s\right){⟩}_{{\Phi }_p\left(s\right)}$ is given by ${\displaystyle \sum _{k=0}^{p-2}(x_k-x_{p-1})s^k}$ . Define $R_p$ to be the matrix that reduces $X\left(s\right)$ modulo ${\Phi }_1\left(s\right)$ and ${\Phi }_p\left(s\right)$ , such thatif $X_0\left(s\right)=⟨X\left(s\right){⟩}_{{\Phi }_1\left(s\right)}$ and $X_1\left(s\right)=⟨X\left(s\right){⟩}_{{\Phi }_p\left(s\right)}$ then

where $X$ , $X_0$ and $X_1$ are vectors formed from the coefficients of $X\left(s\right)$ , $X_0\left(s\right)$ and $X_1\left(s\right)$ . That is,

so that ${\displaystyle R_p=\left[\begin{array}{c}{1}_{-1}\\ G_p\end{array}\right]}$ where $G_p$ is the ${\Phi }_p\left(s\right)$ reduction matrix of size $(p-1)\times p$ . Similarly,let $X\left(s\right)=x_0+x_{1}s+\cdots +x_{p^{e-1}}{s}^{p^{e-1}}$ and define $R_{p^e}$ to be the matrix that reduces $X\left(s\right)$ modulo ${\Phi }_1\left(s\right)$ , ${\Phi }_p\left(s\right)$ , ..., ${\Phi }_{p^e}\left(s\right)$ such that

where as above, $X$ , $X_0$ , ..., $X_e$ are the coefficients of $X\left(s\right)$ , $⟨X\left(s\right){⟩}_{{\Phi }_1\left(s\right)}$ , ..., $⟨X\left(s\right){⟩}_{{\Phi }_{p^e}\left(s\right)}$ .

It turns out that $R_{p^e}$ can be written in terms of $R_p$ . Consider the reduction of $X\left(s\right)=x_0+\cdots +x_8{s}^8$ by ${\Phi }_1\left(s\right)=s-1$ , ${\Phi }_3\left(s\right)=s^2+s+1$ , and ${\Phi }_9\left(s\right)=s^6+s^3+1$ . This is most efficiently performed by reducing $X\left(s\right)$ in two steps. That is, calculate $X^{\text{'}}\left(s\right)=⟨X\left(s\right){⟩}_{s^3-1}$ and $X_2\left(s\right)=⟨X\left(s\right){⟩}_{s^6+s^3+1}$ . Then calculate $X_0\left(s\right)=⟨X^{\text{'}}\left(s\right){⟩}_{s-1}$ and $X_1\left(s\right)=⟨X^{\text{'}}\left(s\right){⟩}_{s^2+s+1}$ . In matrix notation this becomes

Together these become

or

so that $R_9=(R_3\oplus I_6)(R_3\otimes I_3)$ where $\oplus$ denotes the matrix direct sum. Similarly, one finds that $R_{27}=(R_3\oplus I_{24})((R_3\otimes I_3)\oplus I_{18})(R_3\otimes I_9)$ . In general, one has the following.

$R_{p^e}$ is a $p^e\times p^e$ matrix given by ${\displaystyle R_{p^e}=\prod _{k=0}^{e-1}((R_p\otimes I_{p^k})\oplus I_{p^e-p^{k+1}})}$ and can be implemented with $2(p^e-1)$ additions.

The following formula gives the decomposition of a circular convolution into disjoint non-circular convolutions whenthe number of points is a prime power.

It turns out that when $n$ is not a prime power, the reduction of polynomials modulo the cyclotomic polynomial ${\Phi }_n\left(s\right)$ becomes complicated, and with an increasing number of prime factors, the complication increases.Recall, however, that a circular convolution of length $p_1^{e_1}\cdots p_k^{e_k}$ can be converted (by an appropriate permutation) into a $k$ dimensional circular convolution of length $p_i^{e_i}$ along dimension $i$ . By employing this one-dimensional to multi-dimensionalmapping technique, one can avoid having to perform polynomial reductions modulo ${\Phi }_n\left(s\right)$ for non-prime-power $n$ .

The prime factor permutation discussed previously is the permutation that converts a one-dimensional circularconvolution into a multi-dimensional one. Again, we can use the Kronecker product torepresent this. In this case,the reduction operations are applied to each matrix in the following way:

where

The matrix $R_{p_1^{e_1}}\otimes \cdots \otimes R_{p_k^{e_k}}$ can be factored using a property of the Kronecker product. Notice that $(A\otimes B)=(A\otimes I)(I\otimes B)$ , and $(A\otimes B\otimes C)=(A\otimes I)(I\otimes B\otimes I)(I\otimes C)$ (with appropriate dimensions) so that one gets

where $m_i={\prod }_{j=1}^{i-1}{p}_j^{e_j}$ , $n_i={\prod }_{j=i+1}^k{p}_j^{e_j}$ and where the empty product is taken to be 1. This factorization shows that $T$ can be implemented basically by implementing copies of $R_{p^e}$ . There are many variations on this factorizationas explained in [link] . That the various factorization can be interpreted as vectoror parallel implementations is also explained in [link] .