·4 附录A应用：矩阵乘积的快速算法 A.3 Strassen方法 德国数学家Strassen在1969年提出了计算矩阵乘积的快速算法，将运算量降为约O(2.81).下面以 二阶矩阵为例，描述Strassen方法的实现过程.设 A=an an] a21a22 B=bba 则C=AB的每个分量为 C11=a11b1+a12b21,c12=a11b12+a12b22, c21=a21b11+a22b21,c22=a21b12+a22b22. 在Strassen算法中，我们并不直接通过上面的公式来计算C,而是先计算下面7个量： x1=(a11+a22)(b11+b22), x2=(a21+a22)b1: x3=a11(b12-b22, x4=a22(b21-b11, t6=(a11+a12)b22 z6=(a21-a11)(b11+b12, x7=(a12-a22)(b21+b22). 于是，C的各元素可以表示为： C1=C1+x4-T5+r7, G2=x3+工6， c21=x2+T4, c22=x1+3-x2+x6 易知，总共需要做7次乘法和18次加法 下面考虑一般情形.我们采用分而治之的思想，先将矩阵A,B进行2×2分块，即 他a-岛剑 A=A2 Az 则C=AB也可以写成2×2分块形式，即 C1=X1+X4-X5+X7, C12=X3+X5, C21=X2+X, C22=X1+X3-X2+X6 http://math.ecnu.edu.cn/-jypan · 4 · 附录 A 应用: 矩阵乘积的快速算法 A.3 Strassen 方法 德国数学家 Strassen 在 1969 年提出了计算矩阵乘积的快速算法, 将运算量降为约 O(n 2.81). 下面以 二阶矩阵为例, 描述 Strassen 方法的实现过程. 设 A = [ a11 a12 a21 a22] , B = [ b11 b12 b21 b22] . 则 C = AB 的每个分量为 c11 = a11b11 + a12b21, c12 = a11b12 + a12b22, c21 = a21b11 + a22b21, c22 = a21b12 + a22b22. 在 Strassen 算法中, 我们并不直接通过上面的公式来计算 C, 而是先计算下面 7 个量: x1 = (a11 + a22)(b11 + b22), x2 = (a21 + a22)b11, x3 = a11(b12 − b22), x4 = a22(b21 − b11), x5 = (a11 + a12)b22, x6 = (a21 − a11)(b11 + b12), x7 = (a12 − a22)(b21 + b22). 于是, C 的各元素可以表示为: c11 = x1 + x4 − x5 + x7, c12 = x3 + x5, c21 = x2 + x4, c22 = x1 + x3 − x2 + x6. 易知, 总共需要做 7 次乘法和 18 次加法. 下面考虑一般情形. 我们采用分而治之的思想, 先将矩阵 A, B 进行 2 × 2 分块, 即 A = [ A11 A12 A21 A22] , B = [ B11 B12 B21 B22] , 则 C = AB 也可以写成 2 × 2 分块形式, 即 C11 = X1 + X4 − X5 + X7, C12 = X3 + X5, C21 = X2 + X4, C22 = X1 + X3 − X2 + X6, http://math.ecnu.edu.cn/~jypan