Winograd small convolution algorithm

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