<< Chapter < Page | Chapter >> Page > |
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 (\xb7)$ 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] .
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
Notification Switch
Would you like to follow the 'Automatic generation of prime length fft programs' conversation and receive update notifications?