LAFF Week 5 Notes
本章的重点内容:
假设我们有矩阵乘法运算 $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$ 为例,行观点的算法的遍历顺序:
详情可以参考下图:
<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$ 行循环,因此每一次总的循环都是 $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 观点下的算法改用外积得到一个与 $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中)。
具体实现方法待完善。