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 [1], [3], [4].
By interpolating these products,
the product of the two original polynomials can be determined.
In the Winograd short convolution algorithms, this technique
is used and the common points of evaluation are the simple integers,
0, 1, and

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

This linear convolution matrix can be written as

The product

That is,

where

#### Example 1

If

When the interpolation points are 0, 1,and

However,

Similarly, we can write a bilinear form for cyclotomic
convolution.
Let

But since *linear* convolution, then

**Circular Convolution**

By using the Chinese Remainder Theorem for polynomials,
circular convolution can be decomposed into disjoint
cyclotomic convolutions.
Let

and therefore

If

and consequently the circular convolution of

where

Next we consider

then

where

if

Note that the matrix

**The Split Nesting Algorithm**

We now describe the split-nesting algorithm for general
length circular convolution [4].
Let

where

with

where

computes the circular convolution of

As above *linear* convolution.
This is one particular choice for

#### Example 2

A 45 point circular convolution algorithm:

where

and where

**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 [2]. Suppose

as in Equation 18.
When

To explain the matrix exchange property we draw from [2].
Note that

Since

As noted in [2], the matrix exchange property
can be used whenever

Applying the matrix exchange property to Equation 18 one gets

#### Example 3

A 45 point circular convolution algorithm:

where

and where