Difference between revisions of "Winograd small convolution algorithm"
From Encyclopedia of Mathematics
(Importing text file) |
Ulf Rehmann (talk | contribs) m (tex encoded by computer) |
||
| Line 1: | Line 1: | ||
| − | + | <!-- | |
| + | 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 | 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 | 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 | 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 | and is completed by combining these local computations using the formula | ||
| − | + | $$ | |
| + | s ( x ) = \sum _ {k = 1 } ^ { r } s ^ {( k ) } ( x ) e _ {k} ( x ) , | ||
| + | $$ | ||
where | where | ||
| − | + | $$ | |
| + | \left \{ {e _ {k} ( x ) } : {1 \leq k \leq r } \right \} | ||
| + | $$ | ||
| − | is a complete system of idempotents corresponding to the initial factorization of | + | 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
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