Namespaces
Variants
Actions

Difference between revisions of "Winograd small convolution algorithm"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
(details)
 
Line 11: Line 11:
 
{{TEX|done}}
 
{{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 ) $
+
A general strategy for computing linear and cyclic convolutions by applying the polynomial version of the [[Chinese remainder theorem]] [[#References|[a1]]]. For polynomials  $  g ( x ) $
 
and  $  h ( x ) $
 
and  $  h ( x ) $
 
of degree  $  N - 1 $
 
of degree  $  N - 1 $
Line 73: Line 73:
  
 
====References====
 
====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>
+
<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>

Latest revision as of 06:01, 26 May 2024


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=49228
This article was adapted from an original article by R. Tolimieri (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article