Закрыть

Алгоритм Копперсмита — Винограда.

Автор: Васин Алексей
Опубликовано 16.02.2008 в 15:56
Раздел: Численные методы

Умножение матриц по Винограду (не по Копперсмиту—Винограду !) Рассматривая результат умножения двух матриц очевидно, что каждый элемент в нем представляет собой скалярное произведение соответствующих строки и столбца исходных матриц. Такое умножение допускает предварительную обработку, позволяющую часть работы выполнить заранее.

Рассмотрим два вектора 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).

Комментарии (0)

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
Aрхив статей