Namespaces
Variants
Actions

Difference between revisions of "Winograd small convolution algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
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
+
<!--
 +
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.
 +
-->
  
<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>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
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.,
+
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
  
<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>
+
$$
 +
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
 
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>
+
$$
 +
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
 
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>
+
$$
 +
h ^ {( k ) } ( x ) \equiv h ( x ) { \mathop{\rm mod} } m _ {k} ( x ) ,  1 \leq  k \leq  r,
 +
$$
  
<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>
+
$$
 +
g ^ {( k ) } ( x ) \equiv g ( x ) { \mathop{\rm mod} } m _ {k} ( x ) ,  1 \leq  k \leq  r,
 +
$$
  
 
followed by the local computations
 
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>
+
$$
 +
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
 
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>
+
$$
 +
s ( x ) = \sum _ {k = 1 } ^ { r }  s ^ {( k ) } ( x ) e _ {k} ( x ) ,
 +
$$
  
 
where
 
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>
+
$$
 +
\left \{ {e _ {k} ( x ) } : {1 \leq  k \leq  r } \right \}
 +
$$
  
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" />.
+
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]]].
 
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]]].

Revision as of 08:29, 6 June 2020


A general strategy for computing linear and cyclic convolutions by applying the polynomial version of the Chinese remainder theorem [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 [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 [a3].

References

[a1] A. Borodin, I. Munro, "Computational complexity and algebraic and numeric problems" , Amer. Elsevier (1975)
[a2] S. Winograd, "Some bilinear forms whose multiplicative complexity depends on the field of constants" Math. Systems Th. , 10 (1977) pp. 169–180
[a3] R.C. Agarwal, J.W. Cooley, "New algorithms for digital convolution" IEEE Trans. Acoustics, Speech and Signal Processing , 25 (1977) pp. 392–410
How to Cite This Entry:
Winograd small convolution algorithm. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Winograd_small_convolution_algorithm&oldid=18458
This article was adapted from an original article by R. Tolimieri (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article