Содержание

Операция умножения матрицы на матрицу. Есть операция которая принимает на вход две матрицы и выдаёт одну.

Определение

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix},\; B = \begin{bmatrix} b_{11} & b_{12} & \cdots & b_{1q} \\ b_{21} & b_{22} & \cdots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \cdots & b_{nq} \end{bmatrix}.$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$C = \begin{bmatrix} c_{11} & c_{12} & \cdots & c_{1q} \\ c_{21} & c_{22} & \cdots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \cdots & c_{mq} \end{bmatrix}$ ;
где:
$c_{ij} = \sum_{k=1}^n a_{ik}b_{kj} \;\;\; \left(i=1, 2, \ldots m;\; j=1, 2, \ldots q \right)$ .

Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована. В частности, умножение всегда выполнимо, если оба сомножителя являются квадратными матрицами одного и того же порядка.

Следует заметить, что из существования произведения $AB$ вовсе не следует существование произведения $BA$ .

Свойства

Сочетательное свойство:
$\mathbf{A} ( \mathbf{B C} ) = ( \mathbf{A B} ) \mathbf{C}$ ;
$\lambda (\mathbf{AB}) = (\lambda\mathbf{A}) \mathbf{B} = \mathbf{A}(\lambda\mathbf{B})$ .

Распределительное свойство:
$\mathbf{A} ( \mathbf{B} + \mathbf{C} ) = \mathbf{A B} + \mathbf{AC}$ ;
$( \mathbf{A} + \mathbf{B} ) \mathbf{C} = \mathbf{A C} + \mathbf{B C}$ .

Произведение матрицы на единичную матрицу $\mathbf{I}$ подходящего порядка равно самой матрице:
$\mathbf{IA} = \mathbf{A}$ ;
$\mathbf{AI} = \mathbf{A}$ .

Произведение матрицы на нулевую матрицу $\mathbf{0}$ подходящей размерности равно нулевой матрице:
$\mathbf{0A} = \mathbf{0}$ ;
$\mathbf{A0} = \mathbf{0}$ .

Если $\mathbf{A}$ и $\mathbf{B}$ — квадратные матрицы одного и того же порядка, то произведение матриц обладает ещё рядом свойств.

Умножение матриц в целом некоммутативно:
$\mathbf{AB} \ne \mathbf{BA}$ .
Если $\mathbf{AB} = \mathbf{BA}$ , то матрицы $\mathbf{A}$ и $\mathbf{B}$ называются перестановочными или коммутирующими между собой.

Определитель и след произведения не зависят от порядка умножения матриц:
$\det(\mathbf{AB}) = \det(\mathbf{BA}) = \det \mathbf{A} \cdot \det\mathbf{B}$ ;
$\mbox{tr}(\mathbf{AB}) = \mbox{tr}(\mathbf{BA})$ .

Если матрица не вырождена, то у неё есть обратная матрица. Такая что произведение исходной и обратной даёт единичную матрицу.
$AA^{-1} = A^{-1}A = I$ .

Алгоритмы перемножения матриц

Существует большое число алгоритмов умножения. И целый ряд быстрых алгоритмов основанных на группировки операций.

Алгоритм умножения матриц по определению

Код умножения прямоугольных матриц по определению

procedure Mul_Base(Var R:TMatrixNM; A:TMatrixNM; B:TMatrixNM);
var i, j, k: Integer;
 N,M,Q:Integer;
 Tmp:Real;
begin
  M:=RowsCount(A);
  N:=ColumnsCount(A);
  Q:=ColumnsCount(B);
 
  for i:=0 to M-1 do
    for j:=0 to Q-1 do
      begin
	Tmp:=0;
	for k:=0 to N-1 do
	  Tmp:=Tmp+A[i,k]*B[k,j];
        R[i,j]:=Tmp;
      end;
end;

Входные параметры:

Прямоугольная матрица A.
Прямоугольная матрица B.

Выходные параметры:

Прямоугольная матрица R.

Примечание:

Входные параметры не проверяются. Память под матрицу R должна быть выделена. Матрица R должна иметь число строк равные числу строк матрицы A. Матрица R должен иметь число столбцов числу столбцов матрицы A.

Описание:

Умножение согласно определению. $c_{ij} = \sum_{k=1}^n a_{ik}b_{kj} \;\;\; \left(i=1, 2, \ldots m;\; j=1, 2, \ldots q \right)$

Алгоритм умножения с транспонированием

Идея алгоритма в том, что-бы ускорить умножения предварительно транспонировать вторую матрицу. Тогда обращение к элементам второй матрицы будет линейно по памяти, что даёт прирост. См. быстрый(блочный) алгоритм транспонирования.

Помимо ускорения за счёт более оптимального использования доступа к памяти. Возможно использовать аппаратное распараллеливание при помощи команд SIMD(одна инструкция много данных)для ускорения обработки, обрабатывая за раз 4 числа.

В DirectX матрицы мира и вида хранятся и задаются в транспонированном виде. Поэтому во время работы программы матрицы уже транспонированы и их не надо транспонировать.

Код умножения с транспонированием

procedure Transpose_Mul(Var R:TMatrixNM; A:TMatrixNM; B:TMatrixNM);
var i, j, k: Integer;
 N,M,Q:Integer;
 Tmp:Real;
 C:TMatrixNM;
begin
  if IsMatrixTranspose(B) then C:=B 
     else FastTranspose(C,B);  
 
  M:=RowsCount(A);
  N:=ColumnsCount(A);
  Q:=RowsCount(С);
 
  for i:=0 to M-1 do
    for j:=0 to Q-1 do
      begin
	Tmp:=0;
	for k:=0 to N-1 do
	  Tmp:=Tmp+A[i,k]*C[j,k];
        R[i,j]:=Tmp;
      end;
end;

Строки:

Tmp:=0;
for k:=0 to N-1 do
  Tmp:=Tmp+A[i,k]*C[j,k];
R[i,j]:=Tmp;

можно заменить векторным умножением

R[i,j]:=DotProduct(A[i],B[j]);

Строки:

if IsMatrixTranspose(B) then C:=B 
   else FastTranspose(C,B);

Если на перёд известно, что матрица транспонирована, то достаточно вместо этих 2-х строк переименовать C в B.

Блочный алгоритм умножения

$A=\left[\begin{array}{ccccc} A_1 & A_2 \\ A_3 & A_4 \\ \end{array}\right]$ ;

$B=\left[\begin{array}{ccccc} B_1 & B_2 \\ B_3 & B_4 \\ \end{array}\right]$ ;

$C=A*B$ ;

$C=\left[\begin{array}{ccccc} A_1*B_1+A_2*B_3 & A_1*B_2+A_2*B_4 \\ A_3*B_1+A_4*B_3 & A_3*B_2+A_4*B_4 \\ \end{array}\right]$ ;

Алгоритм Штрассена

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

Список литературы:
[1] http://ru.wikipedia.org/wiki/Умножение_матриц
[2] Р. Блейхут Быстрые алгоритмы цифровой обработки сигналов
[3] http://www.youtube.com/watch?v=llwuoLzPbdE
[4] http://msdn.microsoft.com/en-us/library/windows/desktop/bb206269(v=vs.85).aspx