View source for Winograd small convolution algorithm

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w1101001.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w1101002.png" /> of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w1101003.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w1101004.png" />, respectively, the linear convolution

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w1101005.png" /></td> </tr></table>

has degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w1101006.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w1101007.png" />. For any polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w1101008.png" /> of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w1101009.png" />, the linear convolution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w11010010.png" /> can be computed by computing the product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w11010011.png" /> modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w11010012.png" />, i.e.,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w11010013.png" /></td> </tr></table>

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

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w11010014.png" /></td> </tr></table>

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

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w11010015.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w11010016.png" /></td> </tr></table>

followed by the local computations

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w11010017.png" /></td> </tr></table>

and is completed by combining these local computations using the formula

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w11010018.png" /></td> </tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w11010019.png" /></td> </tr></table>

is a complete system of idempotents corresponding to the initial factorization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/w/w110/w110100/w11010020.png" />.

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>