Engineer (AI Inside)

1.引言#

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

2.Strassen 算法#

同理B，C。

于是

引入新矩阵

可得：

3.Block 算法#

比较两段代码：

代码1

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

代码2

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

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

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

4.运用于矩阵乘法#

1
matrixMultBlock(martix A, martix B,martix C,int n)
2
{
3
    /* martix is n x n */
4
    M=16;
5
    for (ii = 0; ii < n; ii+=M) {
6
        for (jj = 0; jj < n; jj+=M) {
7
            for (kk = 0; kk < n; kk+=M) {
8
                for(i=ii; i<ii+M; i++) {
9
                    for(k=kk; k<kk+M; k++) {
10
                        for(j=jj; j<jj+M; j++) {
11
                            C[i][j] += A[i][k]*B[k][j];
12
                        }
13
                    }
14
                }
15
            }
16
        }
17
    }
18
}

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

5.测试#

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

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

表1 算法测试用时（ms）

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.