本质原因: 向量的点积可以分块计算

向量的情形

设 $A, B$ 是两个长度为 $n$ 的两个向量, 则它们的点积

\[AB = \sum_{i=1}^n a_ib_i\]

如果把下标集合 ${1,2,3..,n}$ 任意划分为连续的 $k$ 段,

那么 $A$ 和 $B$ 可以根据此划分形式地写作

\[A=(A_1, A_2, ..., A_k)\] \[B=(B_1,B_2,...,B_k)\]

其中 $A_i, B_i$ 均为向量, 它们各自由上述划分中的第 $i$ 段中的下标所对应的元素构成.

由于下标在划分中保持了原有的对应关系, 所以显然有

\[AB=\sum_{i=1}^k A_iB_i\]

因此, 我们现在可以说, 向量的点积可以分块计算求得.

矩阵情形

现在, 设 $A$ 是 $M*N$ 的矩阵, $B$ 是 $N * P$ 的矩阵, 我们来考虑 $A,B$ 的分块乘法

$A$ 的行被划分为

\[M=M_1+M_2+...+M_r\]

$A$ 的列与 $B$ 的行被划分为

\[N=N_1+N_2+...+N_s\]

$B$ 的列被划分为

\[P=P_1+P_2+...+P_t\]

则有

$A$ 被划分为 $r*s$ 块的形式矩阵, 记为 $A’$ .

形式矩阵 $A’$ 的元素 $A’_{ij}$ 是大小为 $M_i * N_j$ 的矩阵.

$B$ 被划分为 $s*t$ 块的形式矩阵, 记为 $B’$.

形式矩阵 $B’$ 的元素 $B’_{ij}$ 是大小为 $N_i * P_j$ 的矩阵.

对 $A,B$ 进行分块乘法, 即对形式矩阵 $A’,B’$ 进行矩阵乘法

我们来考察分块乘法的结果 $A’B’$ .

任取其中一个元素 $(A’B’)_{ij}$ , 按照形式的矩阵乘法, 有

\[(A'B')_{ij}=A'_{i1}B'_{1j}+A'_{i2}B'_{2j}+...+A'_{is}B'_{sj}\tag{*}\]

右边的和式由 $s$ 个矩阵构成, 它们的大小均为 $M_i*P_j$ ,因此可以彼此相加, 定义出 $(A’B’)_{ij}$

于是, $A’B’$ 中第 i 行的元素均为恰有 $M_i$ 行的矩阵, 完全展开 $A’B’$ 后, 所得矩阵行数恰为

\[M_1+M_2+...+M_r=M\]

同理可知, 完全展开 $A’B’$ 后所得矩阵的列数也恰为 $P$ . 因此分块乘法的结果展开后和 $AB$ 大小相同.

接着我们证明两者元素对应相等.

考虑 $(A’B’)_{ij}$ 的第 $x$ 行第 $y$ 列处所在的元素 $f$ .

记它在展开矩阵中的位置为第 $R(x)$ 行, 第 $C(y)$ 列.

则有

\[R(x)=M_1+M_2+...+M_{i-1}+x\] \[C(y)=P_1+P_2+...+P_{j-1}+y\]

接下来考虑 $f$ 的值. 如果能证明 $f$ 同时恰好为矩阵 $AB$ 在第 $R(x)$ 行第 $C(y)$ 列处的元素,

即若有

\[f=(AB)_{R(x)C(y)}\]

则由 $ijxy$ 的任意性, 完全展开后的 $A’B’$ 与 $AB$ 相等.

由上面的 $(*)$ 式可知, $f$ 的值等于下列矩阵

\[A'_{i1}B'_{1j},A'_{i2}B'_{2j},...,A'_{is}B'_{sj}\]

第 x 行第 y 列处的元素之和.

于是

\[f=\sum_{k=1}^sRow(A'_{ik})_xCol(B'_{kj})_y\]

其中

\[Row(A'_{ik})_x\]

表示矩阵 $A’_{ik}$ 的第 $x$ 行构成的行向量

\[Col(B'_{kj})_y\]

表示矩阵 $B’_{kj}$ 的第 $y$ 列构成的列向量.

由于

\[Row(A'_{i1})_x, Row(A'_{i2})_x,...,Row(A'_{is})_x\]

恰好构成了 $A$ 的第 $R(x)$ 行的一个划分,

\[Col(B'_{1j})_y,Col(B'_{2j})_y,...,Col(B'_{sj})_y\]

恰好构成了 $B$ 的第 $C(y)$ 列的一个划分.且两个划分均为 $s$ 段,

每段长度分别为 $N_1,N_2,…,N_s$

由前面讨论所知的向量点积的可分段性, 有

\[f = Row(A)_R(x)Col(B)_C(y)\]

即 $f$ 的值与 $AB$ 中第 $R(x)$ 行第 $C(y)$ 列的元素相等.

于是, 根据 $f$ 的任意性, 分块相乘所得矩阵 $A’B’$ 完全展开后与 $AB$ 相等. 矩阵分块乘法成立.