二维数组无论在数值计算领域还是在非数值计算领域都是一种相当基本、重要且抽象的数据结构。二维数组在数学中的表现形式是矩阵，因此研究 矩阵的基本运算本质上就是在研究二维数组的运算。显然，尽可能地提高矩阵运算速率对于编程而言是十分重要的工作。

矩阵加法和矩阵乘法是矩阵中基本的矩阵运算。设A、B是两个n×n的矩阵。矩阵的加法表示两个矩阵对应位置元素之和，因此它们的和仍然是一 个n×n的矩阵，记为C=A+B。显然，矩阵加法的时间复杂度为O(n2)。

如果设矩阵A与B的乘积为矩阵C，即C=A×B，显然矩阵C也是一个n×n的矩阵。则矩阵C的第i行第j列的元素C(I,j)等于矩阵A的第i行和矩阵B的第j 列对应元素乘积的和。可表示为：

按这个公式计算C(i,j)需要n次乘法与n-1次加法，而矩阵C中有n×n个元素，因此，由矩阵乘法定义而直接产生的矩阵相乘算法时间复杂度为O(n3) 。

人们长期对矩阵的乘法计算的改进工作做着不懈的努力，做出不少尝试，也试图设计或改进这个算法，但无论怎样改进都囿于O(n3)数量级的时间 复杂度，没有显著地提速。

1969年，斯特拉森（V.Strassen）利用分治策略并加上数学处理设计出了一种时间复杂度是O(n2.81)（准确地说是O(nlog7)）的矩阵相乘算法，宣 称在时间复杂度数量级上有所突破。此结果一发布，立即震动了整个数学界。

为简单描述这一算法，我们假定矩阵C的阶数是2的幂，即存在一个非负正数k使得n=2k。若n不是2的幂，则可通过适当添加全零行和全零列来构造 成2的幂的方阵。

按照分治策略，首先将矩阵A与B分解成4个(n/2)×(n/2)矩阵，即：

对A和B每个(n/2)×(n/2)矩阵进行矩阵乘法运算即可得到C。其中：

C11=A11B11+A12B21

C12=A11B12+A12B22

C21=A21B11+A22B21

C22=A21B12+A22B22

使用通常的矩阵乘法与加法计算分别得到C11、C12、C21、C22四个子矩阵，那么显然可以得出分块子矩阵拼接后的矩阵就是矩阵C。如果分块子矩阵阶 数仍然大于2，则可继续用此方式将分块子矩阵划分为更小的4块，直至每个子矩阵都只有1个元素以至于可以直接计算其乘积为止。对于使用分块子矩 阵计算C的方法，显然需要8次乘法与4次加法，由于每两个n/2级方阵的计算都可以在某个可预见的时间cn2（c是常数）内完成，则通过分治法我们可 以得到T(n)的递归表示方法：

其中b和d是两个常数。求解这个递归关系式：

可以看出，这种方式与通常的矩阵乘法计算时间复杂度一样。究其原因，这种方法仍然是使用8次乘法与4次加法。若无法有效降低乘法的次数，则仍 然无法有效降低时间复杂度。

斯特拉森在分治法的基础上，设计出了一种7次乘法的处理方式。其处理方式是：先使用7个乘法10个加法计算7个等式：

P=(A11+A22)(B11+B22)

Q=(A21+A22)B11

R=A11(B12-B22)

S=A22(B21-B11)

T=(A11+A12)B22

U=(A21-A11)(B11+B12)

V=(A12-A22)(B21+B22)

然后使用8个加法将这7个等式构造成C：

C11=P+S-T+V

C12=R+T

C21=Q+S

C22=P+R-Q+U

以上共使用7次乘法与18次加法。

则由T(n)所得的递归公式是：

推导时间复杂度的过程类似上文，这里不再赘述。终可得时间复杂度为O(nlog7)≈O(n2.81)。

在斯特拉森之后，许多人也试图继续改进该算法。其中，J.E.Hopcroft和L.R.Kerr已经证明，两个2的幂阶矩阵相乘必须要使用7次乘法无法再简化。 若想再进一步简化则必须考虑划分为3的幂或4的幂以及更高级的幂阶才有意义。因此分治策略必须改变，即必须采取其他分治策略的设计思路才行。

后需要说明的是，斯特拉森矩阵乘法目前只有理论意义。事实证明当矩阵阶数足够大（n在128阶以上）时，它和普通的矩阵乘法的执行时间仍无显 著差别。即使如此，斯特拉森矩阵乘法给我们提供了一个有益的启示：即使从简单的定义出发来设计的算法也可能不是好的，仍然可以去优化。

参考文献：

[1]《线性代数与多项式的快速算法》

[2]《计算机算法基础（第三版）》