0.1 Preliminaries

Note that, by inspection,

where $0\le a\le n_1-1$ and $0\le b\le n_2-1$ . Because $n_1$ and $n_2$ are relatively prime a permutation matrix $P$ can be defined by

With this $P$ ,

and

Since $P{S}_n{e}_k=(S_{n_2}\otimes S_{n_1})P{e}_k$ and $P^{-1}=P^t$ , one gets, in the multi-factor case, the following.

If $n=n_1\cdots n_k$ and $n_1,...,n_k$ are pairwise relatively prime, then ${\displaystyle S_n=P^t(S_{n_k}\otimes \cdots \otimes S_{n_1})P}$ where $P$ is the permutation matrix given by ${\displaystyle P{e}_k=e_{⟨k{⟩}_{n_1}+n_1⟨k{⟩}_{n_2}+\cdots +n_1\cdots n_{k-1}⟨k{⟩}_{n_k}}}$ .

This useful permutation will be denoted here as ${\displaystyle P_{n_k,\cdots ,n_1}}$ . If $n=p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}$ then this permutation yields the matrix, $S_{p_1^{e_1}}\otimes \cdots \otimes S_{p_k^{e_k}}$ . This product can be written simply as ${\displaystyle \underset{i=1}{\overset{k}{\otimes }}{S}_{p_i^{e_i}}}$ , so that one has ${\displaystyle S_n=P_{n_1,\cdots ,n_k}^t\left(\underset{i=1}{\overset{k}{\otimes }},S_{p_i^{e_i}}\right)P_{n_1,\cdots ,n_k}}$ .

It is quite simple to show that

In general, one has

A Matlab function for $P_{a,b}\otimes I_s$ is pfp2I() in one of the appendices. This program is a direct implementationof the definition. In a paper by Templeton [link] , another method for implementing $P_{a,b}$ , without `if' statements, is given. That method requires some precalculations, however.A function for $P_{n_1,\cdots ,n_k}$ is pfp() . It uses [link] and calls pfp2I() with the appropriate arguments.

Reduction operations

The Chinese Remainder Theorem for polynomials can be used to decompose a convolution of two sequences(the polynomial product of two polynomials evaluated modulo a third polynomial)into smaller convolutions (smaller polynomial products) [link] . The Winograd $n$ point circular convolution algorithm requires that polynomials are reduced modulo thecyclotomic polynomial factors of $s^n-1$ , ${\Phi }_d\left(s\right)$ for each $d$ dividing $n$ .

When $n$ has several prime divisors the reduction operations become quite complicated and writing a program to implement themis difficult. However, when $n$ is a prime power, the reduction operations are very structured and can be done in a straightforward manner.Therefore, by converting a one-dimensional convolution to a multi-dimensional one, in which the length is a prime poweralong each dimension, the split nesting algorithm avoids the need forcomplicated reductions operations. This is one advantage the split nesting algorithm has overthe Winograd algorithm.

By applying the reduction operations appropriately to the circular shift matrix, we are able to obtain a block diagonal form,just as in the Winograd convolution algorithm. However, in the split nesting algorithm, each diagonal blockrepresents multi-dimensional cyclotomic convolution rather than a one-dimensional one.By forming multi-dimensional convolutions out of one-dimensional ones, it is possible to combine algorithms for smaller convolutions(see the next section). This is a second advantage split nesting algorithm has overthe Winograd algorithm. The split nesting algorithm, however, generally uses more thanthe minimum number of multiplications.

Below we give an explicit matrix description of the required reduction operations, give a program that implements them,and give a formula for the number of additions required. (No multiplications are needed.)