Matrix-Matrix Multiplication
LAFF Week 5 Notes
本章的重点内容：
- 如何从分割的角度去看待矩阵乘法
- 矩阵乘法的性质、转置矩阵、特殊矩阵与矩阵乘法
- 从行、列、RANK 1 的观点看待矩阵乘法和算法
矩阵乘法的分割
假设我们有矩阵乘法运算 $C = AB$，那么该运算可以做如下的分割：
对 $B$ 的水平分割：
$$\left(\begin{array}{c|c}
C_0 & C_1
\end{array}\right)
=
A\left(\begin{array}{c|c}
B_0 & B_1
\end{array}\right)
=\left(\begin{array}{c|c}
AB_0 & AB_1
\end{array}\right)
$$
对 $A$ 的垂直分割：
$$
\left (\frac{C_0}{C_1} \right) = \left (\frac{A_0}{A_1} \right)B = \left (\frac{A_0B}{A_1B} \right)
$$
对 $A$ 的水平分割加上对 $B$ 的垂直分割 ：
这种分割在运算中可以表现为子矩阵的点积：
$$
C = \left(\begin{array}{c|c}
A_0 & A_1
\end{array}\right)\left (\frac{B_0}{B_1} \right) = A_0B_0+A_1B_1
$$
对 $C$ 的十字分割：
该分割实质上就是在做子矩阵的二维矩阵乘法（点积观点，$A$ 的行 乘以 $B$ 的列）
$$\left(\begin{array}{c|c}
C_{00} & C_{01} \\
\hline
C_{10} & C_{11}
\end{array} \right) = \left(\begin{array}{c|c}
A_{00} & A_{01} \\
\hline
A_{10} & A_{11}
\end{array} \right)
\left(\begin{array}{c|c}
B_{00} & B_{01} \\
\hline
B_{10} & B_{11}
\end{array} \right) \\
=\left(\begin{array}{c|c}
A_{00}B_{00} + A_{01}B_{10} & A_{00}B_{01}+A_{01}B_{11} \\
\hline
A_{10}B_{00} + A_{11}B_{10} & A_{10}B_{01}+A_{11}B_{11} \\
\end{array} \right)
$$
需要注意的是，矩阵分割中必须保证对应子矩阵的维度匹配。
矩阵乘法的属性
矩阵乘法的属性
矩阵乘法有如下的属性：
结合律：
$$(AB)C=A(BC)$$
分配律：
分配律对于左乘和右乘都是适用的。
$$A(B+C)=AB+AC$$
$$(A+B)C = AC + BC$$
矩阵乘法与转置
矩阵乘法的转置矩阵等于该乘法因子反转后的转置矩阵相乘:
$$(AB)^T = B^TA^T$$
该性质可以做如下推广：
$$(AB \dots Z)^T = Z^T \dots B^TA^T$$
特殊矩阵的乘法性质
矩阵与单位矩阵
矩阵与单位矩阵的乘积还是其本身：
$$A I = I A = A$$
矩阵与对角矩阵
矩阵与对角矩阵的乘积等于该矩阵的每列乘以对应对角矩阵的元素：
$$
A= \left( \begin{array}{r|r|r|r} a_0 & a_1 & \dots & a_{n-1} \end{array} \right).\\
AD= \left ( \begin{array}{r|r|r|r} \delta_0 a_0 & \delta_1 a_1 & \dots & \delta_{n-1}a_{n-1} \end{array} \right).
$$
该性质也适用于行：
$$
A= \left( \begin{array}{c} \widetilde a_0^{T} \\ \hline \widetilde a_1^{T} \\ \hline \vdots \\ \hline \widetilde a_{m-1}^{T} \end{array} \right)\\
DA= \left ( \begin{array}{c} \delta_0 \widetilde a_0^{T} \\ \hline \delta_1 \widetilde a_1^{T} \\ \hline \vdots \\ \hline \delta_{m-1} \widetilde a_{m-1}^{T} \end{array} \right)
$$
矩阵与三角矩阵
上（下）三角矩阵与上（下）三角矩阵的乘积也是上（下）三角矩阵。
矩阵与对称矩阵
矩阵与其转置矩阵的乘积为对称矩阵。
$$A^TA \,\, \text {is symmetric}$$
转置矩阵与其原矩阵的乘积为对称矩阵。
$$AA^T \,\, \text {is symmetric}$$
对称矩阵的和也是对称矩阵。
$$A+A^TA \,\, \text {is symmetric}$$
对称矩阵的乘积也是对称矩阵。
矩阵乘法算法
从矩阵乘法的定义上看，我们可以通过三层循环来遍历参与运算的矩阵。而这三层循环的顺序是可以改变的；我们可以从行观点、列观点、rank1 观点来看待遍历。而这三种观点反映到算法中则意味着对应的循环在嵌套中的位置。但不管循环位置如何，这三层循环组合在一起实现的都是矩阵元素的遍历。因此不管怎么调整循环的位置，对最后的乘法的结果都是没有关系的。下面我们分别来看看这些不同观点的算法：
列观点算法
以 $C = AB$ 为例，行观点的算法的遍历顺序：
- 最外层循环为 $B$ 中的列循环，即 $j = 0 \to n-1$；
- 中间层循环为 $A$ 中的行循环，即 $ i = 0 \to m-1$;
- 内层循环为 $A、B$ 对应的行列点积，即 $C_{i,j} = \sum^{k-1}_{p=0}\alpha_{i,p}\beta_{p,j}+C_{i,j}$
详情可以参考下图：
<html>
<img src=“/_media/math/linear_algebra/laff/m_m_col_first.svg” width=“500”>
</html>
明白了内部循环实际上是 $A$ 的行与 $B$ 的列的点积以后，那么实际上内部的两层循环（对点积的循环，对 $A$ 的行的循环）组合在一起，就可以表示为：$AB_j$。
因此，针对于最外层对 $B$ 的列 $j$ 的循环，我们可以把内部的循环写成：
$$C_j = AB_j + C_j$$
即 $C$ 的第 $j$ 列 等于 矩阵 $A$ 与 矩阵 $B$ 的第 $j$ 列的乘积结果。因此该算法可以写成：
行观点算法
相对于列观点算法，行观点算法的修改如下：
- 最外层的循环为 $A$ 中的行循环（$i = 0 \to n-1$）
- 中间层的循环为 $B$ 中的列循环 （$j = 0 \to m-1$）
- 内部循环依然是 $A$ 中的行与 $B$ 中的列的点积
因为最外层是 $A$ 行循环，因此每一次总的循环都是 $A$ 的一行依次与 $B$ 中的每一列进行点积。过程参考下图：
<html>
<img src=“/_media/math/linear_algebra/laff/m_m_row_first.svg” width=“500”>
</html>
将内部两层循环合并在一起，就可以表示为：$a_i^TB$。因此，因此，针对于最外层对
$A$ 的列 $i$ 的循环，内部循环可以写成：
$$C_i = a_i^TB + C_i$$
即 $C$ 的第 $i$ 行等于 矩阵 $A$ 的第 $i$ 行与矩阵 $B$ 的乘积结果。因此该算法可以写成：
Rank-1观点算法
比起之前的两种算法，Rank-1 观点下的矩阵乘法的结构如下：
- 最外部的循环为 $p$ 的循环，也就是同时遍历 $A$ 的列 与 $B$ 的行。
- 内部两层循环可以任意选择，无论选择 $A$ 列优先还是 $B$ 行优先，最终得到的结果都是 $A$ 列与 $B$ 行的外积。
可以看到的是，Rank-1 观点下的算法改用外积得到一个与 $C$ 维度相同的矩阵，每一次内部循环对 $C$ 的更新实际上就是将外积得到的矩阵累加到 $C$ 上。来以 $A$ 行优先为例，看看示意图：
<html>
<img src=“/_media/math/linear_algebra/laff/m_m_p_first_r.svg” width=“500”>
</html>
根据上图，每一次内部循环的结果可以写成：$A_iB_j^T$，因此该算法的内部循环为：
$$C = A_iB_j^T+C$$
具体算法如下：
矩阵乘法的优化
关键的思路：减少对内存的读写，尽量将矩阵的乘法分割到每次运算刚好可以在 $CPU$ 的一次操作内完成，（也就是最大限度的利用 CPU 的缓存，将需要反复使用的内容添加到寄存器，L1，L2 cache中）。
具体实现方法待完善。
参考资料
- 所有非 svg 图片均来自 LAFF 课件。