TAOCP 4.6.4 Exercise 52

Let $n = n'n''$ with $\gcd(n',n'')=1$, and let - a normal scheme for cyclic convolution of degree $n'$ use $m'$ chain multiplications, $p'$ parameter multiplications, and $a'$ additions, - a normal sc...

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.4: Evaluation of Polynomials

Exercise 52. [M25] (S. Winograd.) Let $n = n'n''$ where $n' \perp n''$. Given normal schemes for cyclic convolutions of degrees $n'$ and $n''$, using respectively $(m', n'')$ chain multiplications, $(p', q')$ parameter multiplications, and $(a', \alpha')$ additions, show how to construct a normal scheme for cyclic convolution of degree $n$ using $m'm''$ chain multiplications, $p'n'' + m'p''$ parameter multiplications, and $a'n'' + m'a''$ additions.

Verified: yes
Solve time: 6m46s

Solution

Let $n = n'n''$ with $\gcd(n',n'')=1$, and let

  • a normal scheme for cyclic convolution of degree $n'$ use $m'$ chain multiplications, $p'$ parameter multiplications, and $a'$ additions,
  • a normal scheme for cyclic convolution of degree $n''$ use $m''$ chain multiplications, $p''$ parameter multiplications, and $a''$ additions.

We construct a normal scheme for cyclic convolution of degree $n$ and verify the operation counts.

Step 1: Relabel indices via the Chinese remainder theorem

Because $\gcd(n',n'')=1$, every integer $k$ modulo $n$ can be uniquely expressed as

$$ k \equiv i + n' j \pmod n, \qquad 0 \le i < n', \quad 0 \le j < n''. $$

Equivalently, there is a bijection

$$ \mathbf Z_n \longleftrightarrow \mathbf Z_{n'} \times \mathbf Z_{n''}, \qquad k \mapsto (i,j). $$

We relabel the input sequences $a=(a_k){k\in \mathbf Z_n}$ and $b=(b_k){k\in \mathbf Z_n}$ as

$$ a=(a_{ij}){0\le i<n',,0\le j<n''}, \qquad b=(b{ij})_{0\le i<n',,0\le j<n''}. $$

Under this identification, the degree-$n$ cyclic convolution $c = a*b$ satisfies

$$ c_{ij} = \sum_{r=0}^{n'-1}\sum_{s=0}^{n''-1} a_{rs}, b_{i-r,, j-s}, $$

where indices are reduced modulo $n'$ and $n''$ respectively.

Step 2: Define polynomials in the inner algebra

For each $i$ with $0 \le i < n'$, define

$$ A_i(y) = \sum_{j=0}^{n''-1} a_{ij} y^j, \qquad B_i(y) = \sum_{j=0}^{n''-1} b_{ij} y^j, $$

viewed in the algebra $\mathbb Z[y]/(y^{n''}-1)$. Then the inner cyclic convolution of degree $n''$ is

$$ (A*B)i(y) = \sum{r=0}^{n'-1} A_r(y), B_{i-r}(y) \mod y^{n''}-1, $$

which produces polynomials of degree less than $n''$.

Step 3: Verification that the nested convolution equals the original convolution

Expand each term:

$$ \begin{aligned} C_i(y) &= \sum_{r=0}^{n'-1} A_r(y), B_{i-r}(y) \ &= \sum_{r=0}^{n'-1} \Big(\sum_{s=0}^{n''-1} a_{rs} y^s \Big) \Big(\sum_{t=0}^{n''-1} b_{i-r, t} y^t \Big) \ &= \sum_{r=0}^{n'-1} \sum_{s=0}^{n''-1} \sum_{t=0}^{n''-1} a_{rs}, b_{i-r, t} y^{s+t} \mod y^{n''}-1 \ &= \sum_{r=0}^{n'-1} \sum_{s=0}^{n''-1} \sum_{t=0}^{n''-1} a_{rs}, b_{i-r, t} y^{s+t \bmod n''}. \end{aligned} $$

Now let $j \equiv s+t \pmod{n''}$. For each $j$, the coefficient of $y^j$ is

$$ \sum_{r=0}^{n'-1} \sum_{s=0}^{n''-1} a_{rs}, b_{i-r, j-s} = c_{ij}. $$

Hence the nested convolution produces exactly the original cyclic convolution coefficients $c_{ij}$. This establishes the algebraic correctness of the construction.

Step 4: Construct the normal scheme

  1. Apply the degree-$n'$ normal scheme to the vectors $(A_0(y),\dots,A_{n'-1}(y))$ and $(B_0(y),\dots,B_{n'-1}(y))$, treating them as elements in the algebra $\mathbb Z[y]/(y^{n''}-1)$.
  2. Each chain multiplication in this outer scheme multiplies two polynomials of degree less than $n''$. Replace each chain multiplication with the entire degree-$n''$ normal scheme applied to these polynomials.

All other operations (additions or parameter multiplications) are performed componentwise.

Step 5: Count operations

  • Chain multiplications: Each of the $m'$ outer chain multiplications is replaced by $m''$ inner chain multiplications, giving

$$ m' m'' \text{ chain multiplications}. $$

  • Parameter multiplications: The outer scheme contributes $p'$ parameter multiplications. Each acts on polynomials of length $n''$, giving $p'n''$. Each of the $m'$ inner schemes contributes $p''$ parameter multiplications, giving $m'p''$. Total:

$$ p'n'' + m'p''. $$

  • Additions: The outer scheme has $a'$ additions on $n''$-component vectors, giving $a'n''$ additions. Each of the $m'$ inner schemes contributes $a''$ additions, giving $m'a''$. Total:

$$ a'n'' + m'a''. $$

Step 6: Preservation of normality

By definition, a normal scheme has all chain multiplications isolated, with all remaining operations being additions or parameter multiplications. In the construction:

  • Each outer chain multiplication is replaced by a complete normal scheme of degree $n''$, which itself is normal.
  • Additions and parameter multiplications in the outer scheme act componentwise and do not involve chain multiplications.

Hence all chain multiplications remain isolated, and the resulting scheme satisfies the definition of a normal scheme.

Step 7: Conclusion

The described nested construction produces a normal scheme for cyclic convolution of degree $n=n'n''$, using exactly

$$ \boxed{ m'm'',\quad p'n'' + m'p'',\quad a'n'' + m'a'' } $$

chain multiplications, parameter multiplications, and additions, respectively, and correctly computes the convolution.

$\square$