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

Материал из Википедии — свободной энциклопедии

Эту статью следует викифицировать.

Пожалуйста, оформите её согласно правилам оформления статей.

TODO: разбить статью на две

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

Рассмотрим два вектора $V = (v 1, v 2, v 3, v 4)$ и $W = (w 1, w 2, w 3, w 4)$ . Их скалярное произведение равно: $V \cdot W = v_1 w_1 + v_2 w_2 + v_3 w_3 + v_4 w_4$ .

Это равенство можно переписать в виде: $V \cdot W = (v_1 + w_2)(v_2 + w_1) + (v_3 + w_4)(v_4 + w_3) - v_1 v_2 - v_3 v_4 - w_1 w_2 - w_3 w_4$ .

Несмотря на то, что второе выражение требует вычисления большего количества операций, чем первое: вместо четырех умножений - шесть, а вместо трех сложений —- десять, выражение в правой части последнего равенства допускает предварительную обработку: его части можно вычислить заранее и запомнить для каждой строки первой матрицы и для каждого столбца второй, что позволяет выполнять для каждого элемента лишь первые два умножения и последующие пять сложений, а также дополнительно два сложения.

Вот как выглядит полный алгоритм Винограда для умножения матрицы $G$ размером $a \times b$ на матрицу $H$ размером $b \times c$ . Результат записывается в матрицу $R$ размером $a \times 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]. Алгоритм Копперсмита—Винограда имеет асимптотическую сложность $\operatorname{O}(n^{2,375477})$ .