Strassen 算法的一丁点推导(ノ*・ω・)ノ

Strassen Algorithm

此处指的是计算矩阵乘法的那个Strassen算法。

本文假设你了解Strassen算法的流程

推导

我们事后得知这种算法是将原有的\(8\)的乘法结果压缩成了\(7\)个。

我们首先来约定三种small case

3种 small case

3种small case都是经过分成大小相同的块,形成矩阵乘一个向量的形式。

形如下面的样子

\[\begin{pmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{pmatrix}\begin{pmatrix} b_{1} \\ b_{2}\end{pmatrix}\]
1st

第一种为\(a_{11},a_{12},a_{21},a_{22}\)都相等,这个时候乘法结果就是

\[\begin{pmatrix} a(b_{1}+b_{2}) \\ a(b_{1}+b_{2})\end{pmatrix}\]

显然对于这种情况我们只需要实际计算一次矩阵乘法就好了

2nd

第二种情况首先\(a_{11},a_{12},a_{21},a_{22}\)绝对值相等,其次对于符号来说

要么两行的符号不同,要么两列的符号不同

这里给出两行符号不同的情况下的结果。

\[\begin{pmatrix} a(b_{1}+b_{2}) \\ -a(b_{1}+b_{2})\end{pmatrix}\]

可以发现我们也只需要实际计算一次矩阵乘法。

3rd

第三种情况分块后的矩阵要么是上三角矩阵,要么是下三角矩阵,且矩阵不位于对角线上的非零元绝对值等于对角线之差。

形如\(\begin{pmatrix}a_{1}& a_{1}-a_{2} \\ 0 & a_{2}\end{pmatrix}\)

可以发现这种情况下只需要实际计算两次次矩阵乘法。

\[\begin{pmatrix} a_{1}(b_{1}+b_{2}) - a_{2}b_{2} \\ a_{2}b_{2}\end{pmatrix}\]

乘法组的矩阵表示方法

重新回到问题开始,我们要计算两个方阵相乘,记为

\[\begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} \times \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix} = \begin{pmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{pmatrix}\]

显然

\[C_{11} = A_{11}B_{11} + A_{12}B_{21} \\ C_{12}=A_{11}B_{12}+A_{12}B_{22} \\ C_{21}=A_{21}B_{11}+A_{22}B_{21} \\ C_{22}=A_{21}B_{12}+A_{22}B_{22}\]

我们要的其实是这四个分量于是现在将结果展平,如下

\[\begin{pmatrix} C_{11} \\ C_{12} \\ C_{21} \\ C_{22}\end{pmatrix} = \begin{pmatrix} A_{11} & A_{12} & 0 & 0 \\ A_{21} & A_{22} & 0 & 0 \\ 0 & 0 & A_{11} & A_{12} \\ 0 & 0 & A_{21} & A_{22} \end{pmatrix}\begin{pmatrix} B_{11} \\ B_{21} \\ B_{12} \\ B_{22}\end{pmatrix}\]

下一步是将中间这个大的矩阵用上面3种small case拆开。

实测这里拆其实也有技巧,必须挑选对角线上的元素,我试了一次在一行或一列上的时候并不能继续化简(也可能是我sb了,总之我放在最后了,欢迎尝试构造)

\[\begin{pmatrix} A_{11} & A_{12} & 0 & 0 \\ A_{21} & A_{22} & 0 & 0 \\ 0 & 0 & A_{11} & A_{12} \\ 0 & 0 & A_{21} & A_{22} \end{pmatrix} = \begin{pmatrix}A_{11} & -A_{11} & 0 & 0 \\ A_{11} & -A_{11} & 0 & 0 \\ 0 & 0 & -A_{22} & A_{22} \\ 0 & 0 & -A_{22} & A_{22}\end{pmatrix} + \begin{pmatrix}0 & A_{12}+A_{11} & 0 & 0 \\ A_{21}-A_{11} & A_{22}+A_{11} & 0 & 0 \\ 0 & 0 & A_{11}+A_{22} & A_{12}-A_{22} \\ 0 & 0 & A_{21}+A_{22} & 0\end{pmatrix}\]

对于左侧的矩阵再进行分块后(左上角和右下角,便成为了2个case2)可以通过2次乘法得到结果。

而对于右侧的矩阵。

\[ \begin{pmatrix}0 & A_{12}+A_{11} & 0 & 0 \\ A_{21}-A_{11} & A_{22}+A_{11} & 0 & 0 \\ 0 & 0 & A_{11}+A_{22} & A_{12}-A_{22} \\ 0 & 0 & A_{21}+A_{22} & 0\end{pmatrix} = \\ \begin{pmatrix}0 & A_{12}+A_{11} & 0 & 0 \\ A_{21}-A_{11} & 0 & -A_{11}-A_{22} & 0 \\ 0 & -A_{11}-A_{22} & 0 & A_{12}-A_{22} \\ 0 & 0 & A_{21}+A_{22} & 0\end{pmatrix}+\begin{pmatrix}0 & 0 & 0& 0 \\ 0 & A_{11}+A_{22} & A_{11}+A_{22} & 0 \\ 0 & A_{11}+A_{22} & A_{11}+A_{22} & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}\]

其中右侧的矩阵对应于case1,只需要一次乘法就好了

对于等号右侧第一个矩阵来说可以分成两个case3

\[\begin{pmatrix}A_{22}-A_{11} & -A_{11}-A_{22} \\0 & A_{21} + 22\end{pmatrix}, \begin{pmatrix}A_{12}+A_{11} & 0 \\ -A_{11}-A_{22} & A_{12}-A_{22}\end{pmatrix}\]

周围的0就补不了

总之对于本节一开始的大矩阵来说可以分解成这么几个矩阵,一种进行7次乘法就可以得到结果。

参考文献

https://ccjou.wordpress.com/2013/06/04/%E5%88%86%E6%B2%BB%E7%9F%A9%E9%99%A3%E4%B9%98%E6%B3%95%E2%94%80%E2%94%80strassen-%E6%BC%94%E7%AE%97%E6%B3%95/


附录

\[\begin{pmatrix} A_{11} & A_{12} & 0 & 0 \\ A_{21} & A_{22} & 0 & 0 \\ 0 & 0 & A_{11} & A_{12} \\ 0 & 0 & A_{21} & A_{22} \end{pmatrix} = \begin{pmatrix}A_{11} & -A_{11} & 0 & 0 \\ A_{11} & -A_{11} & 0 & 0 \\ 0 & 0 & -A_{12} & A_{12} \\ 0 & 0 & -A_{12} & A_{12}\end{pmatrix} + \begin{pmatrix}0 & A_{12}+A_{11} & 0 & 0 \\ A_{21}-A_{11} & A_{22}+A_{11} & 0 & 0 \\ 0 & 0 & A_{11}+A_{12} & 0 \\ 0 & 0 & A_{21}+A_{12} & A_{22}-A_{12}\end{pmatrix}\]

对于左侧的矩阵再进行分块后(左上角和右下角,便成为了2个case2)可以通过2次乘法得到结果。

而对于右侧的矩阵。

\[ \begin{pmatrix}0 & A_{12}+A_{11} & 0 & 0 \\ A_{21}-A_{11} & A_{22}+A_{11} & 0 & 0 \\ 0 & 0 & A_{11}+A_{12} & 0 \\ 0 & 0 & A_{21}+A_{12} & A_{22}-A_{12}\end{pmatrix} = \\ \begin{pmatrix}0 & 0 & -A_{11}-A_{12} & 0 \\ A_{21}-A_{11} & A_{22}+A_{11} & 0 & 0 \\ 0 & -A_{11}-A_{12} & 0 & 0 \\ 0 & 0 & A_{21}+A_{12} & A_{22}-A_{12}\end{pmatrix}+\begin{pmatrix}0 & A_{12}+A_{11} & A_{12}+A_{11}& 0 \\ 0 & 0 & 0 & 0 \\ 0 & A_{11}+A_{12} & A_{11}+A_{12} & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}\]