114 NUMERIC ALGORITHMS
for j = 2 to d do
columnFactor[i] = columnFactor[i] + H2j-1,i* H2j,i
end for j
end for i// calculate R
for i = 1 to a do
for j = 1 to c do
Ri,j = -rowFactor[i] - columnFactor[j]
for k = 1 to d do
Ri,j = Ri,j + (Gi,2k-1 + H2k,j)*(Gi,2k + H2k-1,j)
end for k
end for j
end for i// add in terms for odd shared dimension
if (2 * (b / 2) ≠ b) then
for i = 1 to a do
for j = 1 to c do
Ri,j = Ri,j + Gi,b* Hb,j
end for j
end for i
end ifAnalysis of Winograd’s Algorithm
Let’s look at the case where the shared dimension (b) is even. We can count the
multiplications and additions as follows:^2
Multiplications AdditionsPreprocessing of G ada (d 1)
Preprocessing of H cdc (d 1)
Computing elements of R acdac (2d + d + 1)
Total
(^2) Under Additions and Computing elements of R, the 2d is from the two additions in
the terms of the product, d is from the sum of the products, and the 1 is from the ini-
tialization of the result.
abcabbc+ +
--------------------------------------------------- 2 -
ab()– 2 ++cb()– 2 ac() 3 b+ 2
------------------------------------------------------------------------------------- 2 -