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

Эту статью следует викифицировать.
Пожалуйста, оформите её согласно общим правилам и указаниям.

Умножение матриц по Винограду Если посмотреть на результат умножения двух матриц, то видно, что каждый элемент в нем представляет собой скалярное произведение соответствующих строки и столбца исходных матриц. Можно заметить также, что такое умножение допускает предварительную обработку, позволяющую часть работы выполнить заранее.

Рассмотрим два вектора 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
 // вычисление rowFactors для G
 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 for j end for i


// вычисление columnFactors для H 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] end for j end for i


// вычисление матрицы R 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

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home