Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

Шаблон:Тупиковая статья

Эту статью следует викифицировать. 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).

Викия-сеть

Случайная вики