0.2 Bilinear forms for circular convolution

Bilinear forms for circular convolution

A basic technique in fast algorithms for convolution is that of interpolation.That is, two polynomials are evaluated at some common points and these values are multiplied [link] , [link] , [link] . By interpolating these products,the product of the two original polynomials can be determined. In the Winograd short convolution algorithms, this techniqueis used and the common points of evaluation are the simple integers, 0, 1, and $-1$ . Indeed, the computational savings of the interpolation techniquedepends on the use of special points at which to interpolate. In the Winograd algorithm the computational savingscome from the simplicity of the small integers. (As an algorithm for convolution, the FFT interpolates over theroots of unity.) This interpolation method is often called the Toom-Cook methodand it is given by two matrices that describe a bilinear form.

We use bilinear forms to give a matrix formulation of the split nesting algorithm.The split nesting algorithm combines smaller convolution algorithms to obtain algorithms for longer lengths.We use the Kronecker product to explicitly describe the way in which smaller convolution algorithms are appropriately combined.

The scalar toom-cook method

First we consider the linear convolution of two $n$ point sequences. Recall thatthe linear convolution of $h$ and $x$ can be represented by a matrix vector product.When $n=3$ :

This linear convolution matrix can be written as $h_0{H}_0+h_1{H}_1+h_2{H}_2$ where $H_k$ are clear.

The product ${\displaystyle \sum _{k=0}^{n-1}{h}_k{H}_{k}x}$ can be found using the Toom-Cook algorithm, an interpolation method.Choose $2n-1$ interpolation points, $i_1,\cdots ,i_{2n-1}$ , and let $A$ and $C$ be matrices given by

That is, $A$ is a degree $n-1$ Vandermonde matrix and $C$ is the inverse of the degree $2n-2$ Vandermonde matrix specified by the same points specifying $A$ . With these matrices, one has

where $*$ denotes point by point multiplication. The terms $Ah$ and $Ax$ are the values of $H\left(s\right)$ and $X\left(s\right)$ at the points $i_1,\cdots i_{2n-1}$ . The point by point multiplication gives thevalues $Y\left(i_1\right),\cdots ,Y\left(i_{2n-1}\right)$ . The operation of $C$ obtains the coefficients of $Y\left(s\right)$ from its values at these points of evaluation. This is the bilinear formand it implies that

However, $A$ and $C$ do not need to be Vandermonde matrices as in [link] . For example, see the two point linear convolution algorithmin the appendix. As long as $A$ and $C$ are matrices such that $H_k=\mathrm{Cdiag}\left(A{e}_k\right)A$ , then the linear convolution of $x$ and $h$ is given by the bilinear form $y=C\{Ah*Ax\}$ . More generally, as long as $A$ , $B$ and $C$ are matrices satisfying $H_k=\mathrm{Cdiag}\left(B{e}_k\right)A$ , then $y=C\{Bh*Ax\}$ computes the linear convolution of $h$ and $x$ . For convenience, if $C\{Ah*Ax\}$ computes the $n$ point linear convolution of $h$ and $x$ (both $h$ and $x$ are $n$ point sequences), then we say “ $(A,B,C)$ describes a bilinear form for $n$ point linear convolution."