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

Определение

Пусть даны две прямоугольные матрицы 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

 
articles/умножение_матрицы_на_матрицу.txt · Последние изменения: 2013/05/26 11:34 От Pavia
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki