| abstract
| - Эту статью следует викифицировать.Категория:Математика:Статьи к викификацииКатегория:Математика:Статьи к викификации TODO: разбить статью на две Умножение матриц по Винограду (не по Копперсмиту—Винограду !) Рассматривая результат умножения двух матриц очевидно, что каждый элемент в нем представляет собой скалярное произведение соответствующих строки и столбца исходных матриц. Такое умножение допускает предварительную обработку, позволяющую часть работы выполнить заранее. Рассмотрим два вектора 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 Представленный код имеет некорректное поведение при b=1, например строчка rowFactor[i] = G[i, 1] * G[i, 2] содержит недопустимый элемент G[i, 2]. Алгоритм Копперсмита—Винограда имеет ассимптотическую сложность O(n^2.375477).
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)