<< Chapter < Page | Chapter >> Page > |
Similarly, we can write a bilinear form for cyclotomic convolution.Let $d$ be any positive integer and let $X\left(s\right)$ and $H\left(s\right)$ be polynomials of degree $\phi \left(d\right)-1$ where $\phi (\xb7)$ is the Euler totient function.If $A$ , $B$ and $C$ are matrices satisfying ${\left({C}_{{\Phi}_{d}}\right)}^{k}=\mathrm{Cdiag}\left(B{e}_{k}\right)A$ for $0\le k\le \phi \left(d\right)-1$ , then the coefficients of $Y\left(s\right)={\u27e8X\left(s\right)H\left(s\right)\u27e9}_{{\Phi}_{d}\left(s\right)}$ are given by $y=C\{Bh*Ax\}$ . As above, if $y=C\{Bh*Ax\}$ computes the $d$ -cyclotomic convolution, then we say “ $(A,B,C)$ describes a bilinear form for ${\Phi}_{d}\left(s\right)$ convolution."
But since ${\u27e8X\left(s\right)H\left(s\right)\u27e9}_{{\Phi}_{d}\left(s\right)}$ can be found by computing the product of $X\left(s\right)$ and $H\left(s\right)$ and reducing the result, a cyclotomic convolution algorithmcan always be derived by following a linear convolution algorithm by the appropriate reductionoperation: If $G$ is the appropriate reduction matrix and if $(A,B,F)$ describes a bilinear form for a $\phi \left(d\right)$ point linear convolution, then $(A,B,GF)$ describes a bilinear form for ${\Phi}_{d}\left(s\right)$ convolution. That is, $y=GF\{Bh*Ax\}$ computes the coefficients of ${\u27e8X\left(s\right)H\left(s\right)\u27e9}_{{\Phi}_{d}\left(s\right)}$ .
By using the Chinese Remainder Theorem for polynomials, circular convolution can be decomposed into disjointcyclotomic convolutions. Let $p$ be a prime and consider $p$ point circular convolution.Above we found that
and therefore
If $({A}_{p},{B}_{p},{C}_{p})$ describes a bilinear form for ${\Phi}_{p}\left(s\right)$ convolution, then
and consequently the circular convolution of $h$ and $x$ can be computed by
where $A=1\oplus {A}_{p}$ , $B=1\oplus {B}_{p}$ and $C=1\oplus {C}_{p}$ . We say $(A,B,C)$ describes a bilinear form for $p$ point circular convolution. Note that if $(D,E,F)$ describes a $(p-1)$ point linear convolution then ${A}_{p}$ , ${B}_{p}$ and ${C}_{p}$ can be taken to be ${A}_{p}=D$ , ${B}_{p}=E$ and ${C}_{p}={G}_{p}F$ where ${G}_{p}$ represents the appropriate reduction operations.Specifically, ${G}_{p}$ is given by Equation 42 from Preliminaries .
Next we consider ${p}^{e}$ point circular convolution.Recall that ${S}_{{p}^{e}}={R}_{{p}^{e}}^{-1}\left({\oplus}_{i=0}^{e},{C}_{{\Phi}_{{p}^{i}}}\right){R}_{{p}^{e}}$ as in Equation 27 from Preliminaries so that the circular convolution is decomposed into a set of $e+1$ disjoint ${\Phi}_{{p}^{i}}\left(s\right)$ convolutions. If $({A}_{{p}^{i}},{B}_{{p}^{i}},{C}_{{p}^{i}})$ describes a bilinear form for ${\Phi}_{{p}^{i}}\left(s\right)$ convolution and if
then $(A{R}_{{p}^{e}},B{R}_{{p}^{e}},{R}_{{p}^{e}}^{-1}C)$ describes a bilinear form for ${p}^{e}$ point circular convolution. In particular, if $({D}_{d},{E}_{d},{F}_{d})$ describes a bilinear form for $d$ point linear convolution, then ${A}_{{p}^{i}}$ , ${B}_{{p}^{i}}$ and ${C}_{{p}^{i}}$ can be taken to be
where ${G}_{{p}^{i}}$ represents the appropriate reduction operation and $\phi (\xb7)$ is the Euler totient function. Specifically, ${G}_{{p}^{i}}$ has the following form
if $p\ge 3$ , while
Note that the matrix ${R}_{{p}^{e}}$ block diagonalizes ${S}_{{p}^{e}}$ and each diagonal block represents a cyclotomic convolution.Correspondingly, the matrices $A$ , $B$ and $C$ of the bilinear form also have a block diagonal structure.
We now describe the split-nesting algorithm for general length circular convolution [link] . Let $n={p}_{1}^{{e}_{1}}\cdots {p}_{k}^{{e}_{k}}$ where ${p}_{i}$ are distinct primes. We have seen that
where $P$ is the prime factor permutation $P={P}_{{p}_{1}^{{e}_{1}},\cdots ,{p}_{k}^{{e}_{k}}}$ and $R$ represents the reduction operations. For example, see Equation 46 in Preliminaries . $RP$ block diagonalizes ${S}_{n}$ and each diagonal block represents a multi-dimensional cyclotomicconvolution. To obtain a bilinear form for a multi-dimensional convolution,we can combine bilinear forms for one-dimensional convolutions.If $({A}_{{p}_{j}^{i}},{B}_{{p}_{j}^{i}},{C}_{{p}_{j}^{i}})$ describes a bilinear form for ${\Phi}_{{p}_{j}^{i}}\left(s\right)$ convolution and if
with
where ${H}_{d}\left(p\right)$ is the highest power of $p$ dividing $d$ , and $\mathcal{P}$ is the set of primes, then $(ARP,BRP,{P}^{t}{R}^{-1}C)$ describes a bilinear form for $n$ point circular convolution. That is
computes the circular convolution of $h$ and $x$ .
As above $({A}_{{p}_{j}^{i}},{B}_{{p}_{j}^{i}},{C}_{{p}_{j}^{i}})$ can be taken to be $({D}_{\phi \left({p}_{j}^{i}\right)},{E}_{\phi \left({p}_{j}^{i}\right)},{G}_{{p}_{j}^{i}}{F}_{\phi \left({p}_{j}^{i}\right)})$ where $({D}_{d},{E}_{d},{F}_{d})$ describes a bilinear form for $d$ point linear convolution. This is one particular choice for $({A}_{{p}_{j}^{i}},{B}_{{p}_{j}^{i}},{C}_{{p}_{j}^{i}})$ - other bilinear forms for cyclotomic convolution that are not derived from linear convolution algorithms exist.
A 45 point circular convolution algorithm:
where
and where $({A}_{{p}_{j}^{i}},{B}_{{p}_{j}^{i}},{C}_{{p}_{j}^{i}})$ describes a bilinear form for ${\Phi}_{{p}_{j}^{i}}\left(s\right)$ convolution.
The matrix exchange property is a useful technique that, under certain circumstances,allows one to save computation in carrying out the action of bilinear forms [link] . Suppose
as in [link] . When $h$ is known and fixed, $Bh$ can be pre-computed so that $y$ can be found using only the operations represented by $C$ and $A$ and the point by point multiplications denoted by $*$ . The operation of $B$ is absorbed into the multiplicative constants.Note that in [link] , the matrix corresponding to $C$ is more complicated than is $B$ . It is therefore advantageous to absorb the workof $C$ instead of $B$ into the multiplicative constants if possible. This can be done when $y$ is the circular convolution of $x$ and $h$ by using the matrix exchange property.
To explain the matrix exchange property we draw from [link] . Note that $y=Cdiag\left(Ax\right)Bh$ , so that $\mathrm{Cdiag}\left(Ax\right)B$ must be the corresponding circulant matrix,
Since $\mathrm{Cdiag}\left(Ax\right)B=J{\left(\mathrm{Cdiag},\left(,A,x,\right),B\right)}^{t}J$ where $J$ is the reversal matrix, one gets
As noted in [link] , the matrix exchange property can be used whenever $y=T\left(x\right)h$ where $T\left(x\right)$ satisfies $T\left(x\right)={J}_{1}T{\left(x\right)}^{t}{J}_{2}$ for some matrices ${J}_{1}$ and ${J}_{2}$ . In that case one gets $y={J}_{1}{B}^{t}\left\{A,x,*,{C}^{t},{J}_{2},h\right\}$ .
Applying the matrix exchange property to [link] one gets
A 45 point circular convolution algorithm:
where $u={C}^{t}{R}^{-t}PJh$ and
and where $({A}_{{p}_{j}^{i}},{B}_{{p}_{j}^{i}},{C}_{{p}_{j}^{i}})$ describes a bilinear form for ${\Phi}_{{p}_{j}^{i}}\left(s\right)$ convolution.
Notification Switch
Would you like to follow the 'Automatic generation of prime length fft programs' conversation and receive update notifications?