Hello zfzhang!



 zfzhang:

Then how does Winograd speedup rather than slowdown convolution computation?


The Winograd matrix-multiplication algorithm does not speed up
convolution.  I am not aware that the Winograd algorithm is ever
used in practice.
Note, the Winograd algorithm does reduce the total number of
additions needed.  The confusion might be that the algorithm is
recursive, and, at a given step in the recursion, the number of
matrix additions is, indeed, larger than in the straightforward
algorithm, but the number of matrix multiplications is reduced,
more than compensating as you recurse down to the bottom.
(Some notes:  The straightforward algorithm for multiplying n x n
matrices has time-complexity O(n^3).  The Winograd algorithm is
one of a series of sub-O(n^3) matrix-multiplication algorithms, but
they are all primarily of purely theoretical interest, and are used
rarely (if ever) in practice.  They only become competitive with the
“naive” algorithm when n is quite large, because, even when
only counting floating-point operations, they have much larger
pre-factors.  Furthermore, they break the benefits of floating-point
pipelines, so, in practice, they make use of significantly fewer
floating-point operations per unit of time.  Nonetheless, this whole
story is quite interesting (if you care about such things).  I believe
it all started with Strassen’s algorithm.)
Best.
K. Frank