Умножение матриц

Умножение матриц

    Матрица - математический объект, эквивалентный двумерному массиву. Числа располагаются в матрице по строкам и столбцам. Числа располагаются в матрице по строкам и столбцам. Две матрицы одинакового размера можно поэлементно сложить или вычесть друг их друга. Если число столбцов в первой матрице совпадает с числом строк во второй, то эти две матрицы можно перемножить. У произведения будет столько же строк, сколько в первой матрице, и столько же столбцов, сколько во второй. При умножении матрицы размером 3 х 4 на матрицу размером 4 х 7 мы получаем матрицу размером 3 х 7. Умножение матриц некоммутативно: оба произведения AB и BA двух квадратных матриц одинакового размера можно вычислить, однако результаты, вообще говоря, будут отличаться друг от друга. (Отметим, что умножение чисел коммутативно, и произведения AB и BA двух чисел A и B равны.)
    Для вычисления произведения двух матриц каждая строка первой почленно умножается на каждый столбец второй. Затем подсчитывается сумма таких произведений и записывается в соответствующую клетку результата. На рисунке 1 приведен пример умножения двух матриц.
    Умножение матриц на рисунке 1 требует 24 умножений и 16 сложений. Вообще, стандартный алгоритм умножения матрицы размером a х b на матрицу размером b х c выполняет abc умножений и a(b - 1)c сложений.
    Вот как выглядит стандартный алгоритм умножения матрицы G размером a x b на матрицу H размером b x c. Результат записывается в матрицу R размером a x c.

for i = 1 to a do
	for j = 1 to c do
		R[i, j] =0 
		for k = 1 to b do
			R[i, j] = R[i, j] + G[i, k]*H[k, j]
		end for k
	end for j
end for i

На первый взгляд это минимальный объем работы, необходимый для перемножения двух матриц. Однако исследователям не удалось доказать минимальность, и в результате они обнаружили другие алгоритмы, умножающие матрицы более эффективно.

Умножение матриц по Винограду

    Если посмотреть на результат умножения двух матриц, то видно, что каждый элемент в нем представляет собой скалярное произведение соответствующих строки и столбца исходных матриц. Можно заметить также, что такое умножение допускает предварительную обработку, позволяющую часть работы выполнить заранее.
    Рассмотрим два вектора 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. Результаты подсчета сложений и умножений сведены в следующую таблицу.

	Умножения	Сложения
Предварительная обработка матрицы G	ad	a(d - 1)
Предварительная обработка матрицы H	cd	c(d - 1)
Вычисление матрицы R	acd	ac(2d + d + 1)
Всего	(abc + ab + bc)/2	(a(b - 2) + c(b - 2) + ac(3b + 2))/2

Умножение матриц по Штрассену

Алгоритм Штрассена работает с квадратными матрицами. На самом деле он настолько эффективен, что иногда разумно расширить матрицы до квадратных, и при этом он все равно дает выигрыш, превышающий расходы на введение дополнительных элементов.
Для умножения матриц алгоритм Штрассена использует семь формул. Эти формулы чрезвычайно неестественны и, к сожалению, в оригинальной статье Штрассена не объясняется, как он пришел к ним. Замечательно, что как сами формулы, так и их использование не требуют, чтобы умножение элементов матриц было коммутативным. Это означает, в частности, что сами эти элементы могут быть матрицами, а значит, алгоритм Штрассена можно применять рекурсивно. Вот формулы Штрассена:

x1 = (G1,1 + G2,2)(H1,1 + H2,2);	x5 = (G1,1 + G2,2)H2,2;
x2 = (G2,1 + G2,2)H1,1;	x6 = (G2,1 - G1,1)(H1,1 + H1,2);
x3 = G1,1(H1,2 - H2,2);	x7 = (G2,1 - G2,2)(H2,1 + H2,2)
x4 = G2,2(H2,1 - H1,1);

Теперь элементы матрицы R могут вычисляться по формулам:

R1,1 = x1 + x4 - x5 + x7;	R1,2 = x3 + x5;
R2,1 = x2 + x4;	R2,2 = x1 + x3 - x2 + x6.

При умножении двух 2 х 2-матриц алгоритм выполняет 7 умножений и 18 сложений. Экономия не видна: мы получили 14 сложений в обмен на одно умножение в стандартных алгоритмах. Анализ общего случая показывает, что число умножений при перемножении двух N x N-матриц приблизительно равно N^2.81, а число сложений 6N^2.81 - 6N². При умножении двух 16 х 16-матриц алгоритм Штрассена экономит 1677 умножений за счет дополнительных 9138 сложений.
Сводя три результата воедино, мы получаем следующую картину.

	Умножения	Сложения
Стандартный алгоритм	N³	N³ - N²
Алгоритм Винограда	(N³ + 2N²)/2	(3N³ + 4N² - 4N)/2
Алгоритм Штрассена	N^2.81	6N^2.81 - 6N²

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

Сайт управляется системой uCoz