0.1 Preliminaries  (Page 2/5)

The Winograd Structure can be described in this manner also. Suppose $M\left(s\right)$ can be factored as $M\left(s\right)=M_1\left(s\right)M_2\left(s\right)$ where $M_1$ and $M_2$ have no common roots, then $C_M\sim \left(C_{M_1},\oplus ,C_{M_2}\right)$ where $\oplus$ denotes the matrix direct sum. Using this similarity and recalling [link] , the original convolution is decomposed intodisjoint convolutions. This is, in fact, a statement of the Chinese Remainder Theoremfor polynomials expressed in matrix notation. In the case of circular convolution, $s^n-1={\prod }_{d|n}{\Phi }_d\left(s\right)$ , so that $S_n$ can be transformed to a block diagonal matrix,

where ${\Phi }_d\left(s\right)$ is the $d^{th}$ cyclotomic polynomial. In this case, each block represents a convolutionwith respect to a cyclotomic polynomial, or a `cyclotomic convolution'.Winograd's approach carries out these cyclotomic convolutions using the Toom-Cook algorithm.Note that for each divisor, $d$ , of $n$ there is a corresponding block on the diagonal of size $\phi \left(d\right)$ , for the degree of ${\Phi }_d\left(s\right)$ is $\phi \left(d\right)$ where $\phi (·)$ is the Euler totient function. This method is good for short lengths, butas $n$ increases the cyclotomic convolutions become cumbersome,for as the number of distinct prime divisors of $d$ increases, the operation described by ${\sum }_k{h}_k{\left(C_{{\Phi }_d}\right)}^k$ becomes more difficult to implement.

The Agarwal-Cooley Algorithm utilizes the fact that

where $n=n_1{n}_2$ , $(n_1,n_2)=1$ and $P$ is an appropriate permutation [link] . This converts the one dimensional circular convolutionof length $n$ to a two dimensional one of length $n_1$ along one dimension and length $n_2$ along the second.Then an $n_1$ -point and an $n_2$ -point circular convolution algorithm can be combined to obtain an $n$ -point algorithm. In polynomial notation, the mapping accomplished bythis permutation $P$ can be informally indicated by

It should be noted that [link] implies that a circulant matrix of size $n_1{n}_2$ can be written as a block circulant matrix with circulantblocks.

The Split-Nesting algorithm [link] combines the structures of the Winograd and Agarwal-Cooley methods, so that $S_n$ is transformed to a block diagonalmatrix as in [link] ,

Here $\Psi \left(d\right)={\otimes }_{p|d,p\in \mathcal{P}}{C}_{{\Phi }_{H_d\left(p\right)}}$ where $H_d\left(p\right)$ is the highest power of $p$ dividing $d$ , and $\mathcal{P}$ is the set of primes.

In this structure a multidimensional cyclotomic convolution, represented by $\Psi \left(d\right)$ , replaces each cyclotomic convolution in Winograd's algorithm (represented by $C_{{\Phi }_d}$ in [link] . Indeed, if the product of $b_1,\cdots ,b_k$ is $d$ and they are pairwise relatively prime, then $C_{{\Phi }_d}\sim C_{{\Phi }_{b_1}}\otimes \cdots \otimes C_{{\Phi }_{b_k}}$ . This gives a method for combining cyclotomic convolutionsto compute a longer circular convolution. It is like the Agarwal-Cooley method but requires feweradditions [link] .

Prime factor permutations

One can obtain $S_{n_1}\otimes S_{n_2}$ from $S_{n_1{n}_2}$ when $(n_1,n_2)=1$ , for in this case, $S_n$ is similar to $S_{n_1}\otimes S_{n_2}$ , $n=n_1{n}_2$ . Moreover, they are related by a permutation.This permutation is that of the prime factor FFT algorithms and is employed in nesting algorithmsfor circular convolution [link] , [link] . The permutation is described by Zalcstein [link] , among others, and it is his description we draw on in the following.

Let $n=n_1{n}_2$ where $(n_1,n_2)=1$ . Define $e_k$ , ( $0\le k\le n-1$ ), to be the standard basis vector, ${(0,\cdots ,0,1,0,\cdots ,0)}^t$ , where the 1 is in the $k^{th}$ position. Then, the circular shift matrix, $S_n$ , can be described by