View source for Winograd small convolution algorithm

<!--
w1101001.png
$#A+1 = 20 n = 0
$#C+1 = 20 : ~/encyclopedia/old_files/data/W110/W.1100100 Winograd small convolution algorithm
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

A general strategy for computing linear and cyclic convolutions by applying the polynomial version of the [[Chinese remainder theorem|Chinese remainder theorem]] [[#References|[a1]]]. For polynomials  $  g ( x ) $
and  $  h ( x ) $
of degree  $  N - 1 $
and  $  M - 1 $, 
respectively, the linear convolution

$$ 
s ( x ) = h ( x ) g ( x )
$$

has degree  $  L - 1 $, 
where  $  L = M + N - 1 $. 
For any polynomial  $  m ( x ) $
of degree  $  L $, 
the linear convolution  $  s ( x ) $
can be computed by computing the product  $  h ( x ) g ( x ) $
modulo  $  m ( x ) $, 
i.e.,

$$ 
s ( x ) \equiv s ( x ) { \mathop{\rm mod} } m ( x ) .
$$

The Chinese remainder theorem permits this computation to be localized. Choose a factorization

$$ 
m ( x ) = m _ {1} ( x ) \dots m _ {r} ( x )
$$

into relatively prime factors. The Winograd small convolution algorithm proceeds by first computing the reduced polynomials

$$ 
h ^ {( k ) } ( x ) \equiv h ( x ) { \mathop{\rm mod} } m _ {k} ( x ) ,  1 \leq  k \leq  r,
$$

$$ 
g ^ {( k ) } ( x ) \equiv g ( x ) { \mathop{\rm mod} } m _ {k} ( x ) ,  1 \leq  k \leq  r,
$$

followed by the local computations

$$ 
s ^ {( k ) } ( x ) \equiv h ^ {( k ) } g ^ {( k ) } ( x ) { \mathop{\rm mod} } m _ {k} ( x ) ,  1 \leq  k \leq  r,
$$

and is completed by combining these local computations using the formula

$$ 
s ( x ) = \sum _ {k = 1 } ^ { r }  s ^ {( k ) } ( x ) e _ {k} ( x ) ,
$$

where

$$ 
\left \{ {e _ {k} ( x ) } : {1 \leq  k \leq  r } \right \}
$$

is a complete system of idempotents corresponding to the initial factorization of  $  m ( x ) $.

S. Winograd [[#References|[a2]]] expanded on this general strategy by developing bilinear algorithms for computing the product of polynomials modulo a polynomial. Within this general strategy, these bilinear algorithms permit one to use small efficient algorithms as building blocks for larger-size algorithms [[#References|[a3]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Borodin,   I. Munro,   "Computational complexity and algebraic and numeric problems" , Amer. Elsevier  (1975)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  S. Winograd,   "Some bilinear forms whose multiplicative complexity depends on the field of constants"  ''Math. Systems Th.'' , '''10'''  (1977)  pp. 169–180</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.C. Agarwal,   J.W. Cooley,   "New algorithms for digital convolution"  ''IEEE Trans. Acoustics, Speech and Signal Processing'' , '''25'''  (1977)  pp. 392–410</TD></TR></table>