结合 Block 算法的 Strassen 矩阵乘法

1.引言

对于矩阵乘法，常规算法是进行三重循环求解，复杂度显然 O($n^{3}$)。对此可使用 strassen 算法进行优化，复杂度降低到 O($n^{2.81}$)。实际测试中时间虽然比传统方法快，但仍然耗时。本文介绍一种结合 Block 算法的 strassen 算法优化，测试将2048规模矩阵乘法用时降低几秒。

2.Strassen 算法

$A= \begin{bmatrix} A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{bmatrix}$

同理B，C。

于是

$C_{1,1}=A_{1,1}B_{1,1}+A_{1,2}B_{2,1}\\\\ C_{1,2}=A_{1,1}B_{1,2}+A_{1,2}B_{2,2}\\\\ C_{2,1}=A_{2,1}B_{1,1}+A_{2,2}B_{2,1}\\\\ C_{2,2}=A_{2,1}B_{1,2}+A_{2,2}B_{2,2}$

引入新矩阵

${M}_{1}= ({A}_{1,1} + {A}_{2,2})({B}_{1,1} + {B}_{2,2})\\\\ {M}_{2} = ({A}_{2,1} + {A}_{2,2}) {B}_{1,1}\\\\ {M}_{3} = {A}_{1,1} ({B}_{1,2} - {B}_{2,2})\\\\ {M}_{4} = {A}_{2,2} ({B}_{2,1} - {B}_{1,1})\\\\ {M}_{5} = ({A}_{1,1} + {A}_{1,2}) {B}_{2,2}\\\\ {M}_{6} = ({A}_{2,1} - {A}_{1,1}) ({B}_{1,1} + {B}_{1,2})\\\\ {M}_{7} = ({A}_{1,2} - {A}_{2,2}) ({B}_{2,1} + {B}_{2,2})$

可得：

${C}_{1,1} = {M}_{1} + {M}_{4} - {M}_{5} + {M}_{7}\\\\ {C}_{1,2} = {M}_{3} + {M}_{5}\\\\ {C}_{2,1} = {M}_{2} + {M}_{4}\\\\ {C}_{2,2} = {M}_{1} - {M}_{2} + {M}_{3} + {M}_{6}$

3.Block 算法

比较两段代码：

代码1

s=0;
for(i=0;i<n;i++){
    s+=a[i];
}

代码2

s1=0;s2=0;
for(i=0;i<n-2;i+=2){
    s1+=a[i];
    s2+=a[i+1];
}
s=s1+s2;

由代码2可见在一次循环中做了两次加和，显然比代码1要快速。

因此 Block 算法即将循环展开，一次进行复数运算达到提高处理速度的目的。

4.运用于矩阵乘法

matrixMultBlock(martix A, martix B,martix C,int n) 
{
    /* martix is n x n */
    M=16;
    for (ii = 0; ii < n; ii+=M) {
        for (jj = 0; jj < n; jj+=M) {
            for (kk = 0; kk < n; kk+=M) {
                for(i=ii; i<ii+M; i++) {
                    for(k=kk; k<kk+M; k++) {
                        for(j=jj; j<jj+M; j++) {
                            C[i][j] += A[i][k]*B[k][j];
                        }
                    }
                }
            }
        }
    }
}

由文献得分块取16时效果较好[1]

5.测试

分别用两种算法在1024、2048规模下测试，重复3次。

测试环境:Intel Core i5 4258U (2.4GHz),4G RAM

表1 算法测试用时（ms）

规模	次数	strassen	strassen with block
1024	1	11558	7814
	2	9929	7262
	3	8393	7363
2048	1	52950	51274
	2	54158	51989
	3	57490	56193

$\overline{T}_{s,1024}=9960ms\\\\ \overline{T}_{swb,1024}=7480ms\\\\ \Delta T_{1024}=2480ms=2.48s\\\\ \overline{T}_{s,2048}=54860ms\\\\ \overline{T}_{swb,2048}=53152ms\\\\ \Delta T_{2048}=1708ms=1.708s$

6.结论

经过测试，结合 Block 算法的 Strassen 矩阵乘法较普通的最大减少2.48秒，时间效率有所提高，但更高效的优化还需探索。

参考文献

[1] Kouya T. Accelerated multiple precision matrix multiplication using Strassen’s algorithm and Winograd’s variant[J]. JSIAM Letters, 2014, 6(0): 81-84.