Умножение матриц по Винограду (не по Копперсмиту—Винограду !) Рассматривая результат умножения двух матриц очевидно, что каждый элемент в нем представляет собой скалярное произведение соответствующих строки и столбца исходных матриц. Такое умножение допускает предварительную обработку, позволяющую часть работы выполнить заранее.
Рассмотрим два вектора V = (v1, v2, v3, v4) и W = (w1, w2, w3, w4). Их скалярное произведение равно: V • W = v1w1 + v2w2 + v3w3 + v4w4.
Это равенство можно переписать в виде: V • W = (v1 + w2)(v2 + w1) + (v3 + w4)(v4 + w3) — v1v2 — v3v4 — w1w2 — w3w4.
Несмотря на то, что второе выражение требует вычисления большего количества операций, чем первое: вместо четырех умножений - шесть, а вместо трех сложений - десять, выражение в правой части последнего равенства допускает предварительную обработку: его части можно вычислить заранее и запомнить для каждой строки первой матрицы и для каждого столбца второй, что позволяет выполнять для каждого элемента лишь первые два умножения и последующие пять сложений, а также дополнительно два сложения.
Вот как выглядит полный алгоритм Винограда для умножения матрицы G размером a x b на матрицу H размером b x c. Результат записывается в матрицу R размером a x c.
d = b/2;
for i = 1 to a do
rowFactor[i] = G[i, 1] * G[i, 2]
for j = 2 to d do
rowFactor[i] = rowFactor[i] + G[i, 2j — 1] * G[i, 2j]
end;
end;
for i = 1 to c do
columnFactor[i] = H[1, i] * H[2, i]
for j = 2 to d do
columnFactor[i] = columnFactor[i] + H[2j — 1, i] * H[2j, i]
for i = 1 to a do
for j = 1 to c do
R[i, j] = -rowFactor[i] — columnFactor[j]
for k = 1 to d do
R[i, j]=R[i, j]+(G[i, 2k-1]+H[2k, j])*(G[i, 2k] + H[2k-1, j])
end for k
end for j
end for i
if (2 * (b/2) /= b) then
for i = 1 to a do
for j = 1 to c do
R[i, j] = R[i, j] + G[i, b] * H[b, j]
end for j
end for i
end if
Представленный код имеет некорректное поведение при b=1, например строчка rowFactor[i] = G[i, 1] * G[i, 2] содержит недопустимый элемент G[i, 2]. Алгоритм Копперсмита—Винограда имеет ассимптотическую сложность O(n^2.375477).
