======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}$
\\
\\
详情可以参考下图：
\\
\\
\\
明白了内部循环实际上是 $A$ 的行与 $B$ 的列的点积以后，那么实际上内部的两层循环（对点积的循环，对 $A$ 的行的循环）组合在一起，就可以表示为：$AB_j$。
\\
\\
因此，针对于最外层对 $B$ 的列 $j$ 的循环，我们可以把内部的循环写成：
$$C_j = AB_j + C_j$$
即 $C$ 的第 $j$ 列 等于 矩阵 $A$ 与 矩阵 $B$ 的第 $j$ 列的乘积结果。因此该算法可以写成：
\\
\\
{{ math:linear_algebra:laff:5_3_2_algorithm.png?600 |}}
\\
\\
===行观点算法===
相对于列观点算法，行观点算法的修改如下：
* 最外层的循环为 $A$ 中的行循环（$i = 0 \to n-1$）
* 中间层的循环为 $B$ 中的列循环 （$j = 0 \to m-1$）
* 内部循环依然是 $A$ 中的行与 $B$ 中的列的点积
因为最外层是 $A$ 行循环，因此每一次总的循环都是 $A$ 的一行依次与 $B$ 中的每一列进行点积。过程参考下图：
\\
\\
\\
\\
将内部两层循环合并在一起，就可以表示为：$a_i^TB$。因此，因此，针对于最外层对
$A$ 的列 $i$ 的循环，内部循环可以写成：
$$C_i = a_i^TB + C_i$$
即 $C$ 的第 $i$ 行等于 矩阵 $A$ 的第 $i$ 行与矩阵 $B$ 的乘积结果。因此该算法可以写成：
\\
\\
{{ math:linear_algebra:laff:5_3_3_algorithm.png?600 |}}
\\
\\
===Rank-1观点算法===
比起之前的两种算法，//Rank-1// 观点下的矩阵乘法的结构如下：
* 最外部的循环为 $p$ 的循环，也就是同时遍历 $A$ 的列 与 $B$ 的行。
* 内部两层循环可以任意选择，无论选择 $A$ 列优先还是 $B$ 行优先，最终得到的结果都是 $A$ 列与 $B$ 行的**外积**。
可以看到的是，//Rank-1// 观点下的算法改用**外积**得到一个与 $C$ 维度相同的矩阵，每一次内部循环对 $C$ 的更新实际上就是将外积得到的矩阵累加到 $C$ 上。来以 $A$ 行优先为例，看看示意图：
\\
\\
\\
\\
根据上图，每一次内部循环的结果可以写成：$A_iB_j^T$，因此该算法的内部循环为：
$$C = A_iB_j^T+C$$
\\
\\
具体算法如下：
\\
\\
{{ math:linear_algebra:laff:5_5_2_summary10.png?600 |}}
\\
====矩阵乘法的优化====
关键的思路：**减少对内存的读写**，尽量将矩阵的乘法分割到每次运算刚好可以在 $CPU$ 的一次操作内完成，（也就是最大限度的利用 CPU 的缓存，将需要反复使用的内容添加到寄存器，L1，L2 cache中）。
具体实现方法待完善。
====参考资料====
* 所有非 svg 图片均来自 LAFF 课件。
* [[https://github.com/flame/how-to-optimize-gemm/wiki|矩阵的优化 wiki]]
