Strassen's Algorithm

封面来自Swift Algorithm Club: Strassen’s Algorithm | Kodeco

对于正常情况，矩阵乘法需要$\mathcal{O}(n^3)$的时间复杂度（假设$m,p=n$）

考虑分块矩阵$C = AB$

$$A=\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix},\quad B=\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix},\quad C=\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}$$

矩阵乘法可以表示为

$$\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}=\begin{bmatrix}A_{11}\times B_{11}+A_{12}\times B_{21}&A_{11}\times B_{12}+A_{12}\times B_{22}\\A_{21}\times B_{11}+A_{22}\times B_{21}&A_{21}\times B_{12}+A_{22}\times B_{22}\end{bmatrix}.$$

总共需要需要8次乘法和4次加法。另一种理解方式（递归情况下）：矩阵每增加一倍，计算开销是原来的8倍$\rightarrow \mathcal{O}(n^3)$ 。因此如果可以减少乘法运算的次数，就可以加快矩阵乘法的计算。

定义

$$\begin{align*}&M_{1}=(A_{11}+A_{22})\times(B_{11}+B_{22});\\&M_{2}=(A_{21}+A_{22})\times B_{11};\\&M_{3}=A_{11}\times(B_{12}-B_{22});\\&M_{4}=A_{22}\times(B_{21}-B_{11});\\&M_{5}=(A_{11}+A_{12})\times B_{22};\\&M_{6}=(A_{21}-A_{11})\times(B_{11}+B_{12});\\&M_{7}=(A_{12}-A_{22})\times(B_{21}+B_{22}),\end{align*}$$

则：

$$\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}=\begin{bmatrix}M_1+M_4-M_5+M_7&M_3+M_5\\M_2+M_4&M_1-M_2+M_3+M_6\end{bmatrix}.$$

该方法总共只需要7次乘法，但是加法增加到了18次。

复杂度计算

令$f(n)$表示矩阵乘法的复杂度，$g(n)$表示矩阵加法的复杂度，则有：

$$f(n) = 7f(\frac n2)+18g(\frac n2)$$

其中$f$是一个$\mathcal{O}(n^p), 2<p\leq3$的阶，$g$是$\mathcal{O}(n^2)$阶。因此省略掉$g$，则有：

$$\begin{align*} f(n) &= 7f(\frac n2)=7^2f(\frac n 4)\\ &= 7^{\log_2 n-1}f(\frac n {2^{\log_2 n-1}})=7^{\log_2 n-1}f(2)\\ &= 2^{\log_2 7(\log_2n-1)}f(2)=2^{\log_2n\log_2 7}/2^{\log_27}f(2)\\ &= Cn^{\log_27} \end{align*}$$

因此Strassen’s Algorithm的复杂度为$\mathcal{O}(n^{\log_27})\approx\mathcal{O}(n^{2.8})$