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

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