0.2 Bilinear forms for circular convolution  (Page 2/2)

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 (·)$ 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)={⟨X\left(s\right)H\left(s\right)⟩}_{{\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 ${⟨X\left(s\right)H\left(s\right)⟩}_{{\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 ${⟨X\left(s\right)H\left(s\right)⟩}_{{\Phi }_d\left(s\right)}$ .

Circular convolution

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 (·)$ 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.

The split nesting algorithm

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.

The matrix exchange property

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 ${\displaystyle \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 ${\displaystyle y=J_1{B}^t\left\{A,x,*,C^t,J_2,h\right\}}$ .

Applying the matrix exchange property to [link] one gets