直接按照定义计算两个n阶实数方阵的乘积需要进行​\( n^3 \)​次实数乘法

如果将方阵分割，按照矩阵的分块乘法去计算，看似通过递归化简了问题，实际上完成乘法的复杂度依然是​\( \Theta (n^3) \)​。因为矩阵分块之后分治为了八次小矩阵乘法，然后进行矩阵加法，递推式 \(T(n) = 8T(\frac{n}{2}) + \Theta(n²)\)给出的这种方法的解，依然是\( \Theta (n^3) \)

而strassen算法给出了一个复杂度为​\( \Theta (n^{\log _{2} 7}) \)​\( \approx\Theta( n^{2.81}) \)的算法

一个相关的例子

设复数

$$x=a+bi$$

$$y=c+di$$

求\(xy\)

最naive的方法就是\(xy=(a+bi)(c+di)=(ac-bd)+(ad+bc)i\)， 直接需要算出这个答案需要四次实数乘法(ac bd ad bc)

然而实际上，不需要四次乘法，而只需要三次就够：

$$ac-bd=a(c+d)-d(a+b)$$

$$ad+bc=d(a+b)-b(d-c)$$

能进行这样的化简，本质上在于我们需要的并不是ac bd ad bc这四个值，而是关于它们的两个方程，所以实际上需要的未知量少于四个，也就有可能减少实数乘法的次数。

strassen算法

要计算矩阵A和B的乘积\(C=AB\)，先将矩阵分块分解为

$$A_{11}\ A_{12}\ A_{21}\ A_{22}\ B_{11}\ B_{12}\ B_{21}\ B_{22}$$

然后不直接计算目标的C的几个分块，而是先计算这个中间结果：

然后不直接计算目标的C的几个分块，而是先计算这个中间结果：

$S_1=B_{12}-B_{22}$

$$S_2=A_{11}+A_{12}$$

$$S_3=A_{21}+A_{22}$$

$$S_4=B_{21}-B_{11}$$

$$S_5=A_{11}+A_{22}$$

$$S_6=B_{11}+B_{22}$$

$$S_7=A_{12}-A_{22}$$

$$S_8=B_{21}+B_{22}$$

$$S_9=A_{11}-A_{21}$$

$$S+{10}=B_{11}+B_{12}$$

接着计算7次矩阵乘法

$$P_1=A_{11}\cdot S_1$$

$$P_2=S_2\cdot B_{22}$$

$$P_3=S_3\cdot B_{11}$$

$$P_4=A_{22}\cdot S_4$$

$$P_5=S_5\cdot S_6$$

$$P_6=S_7\cdot S_8$$

$$P_7=S_9\cdot S_{10}$$

最后，根据这7个结果就可以计算出C矩阵

$$C_{11}=P_5+P_4-P_2+P_6$$

$$C_{12}=P_1+P_2$$

$$C_{21}=P_3+P_4$$

$$C_{22}=P_5+P_1-P_3-P_7$$

和刚才那个例子一样，本质上还是很利用了线性相关的特点。

这个算法的复杂度递推式是

$$T(n)=7T(\frac{n}{2})+\Theta(n^2)$$

它的解就是开头所说的

​$$ \Theta (n^{\log _{2} 7}) ​\approx\Theta( n^{2.81}) $$