这个递归方程的解仍然是T(n)=O(m)。因此 该方法并不比用原始定义直接计算更有效。究其原 只用7次乘法运算 因,乃是由于该方法并没有减少矩阵的乘法次数 而矩阵乘法耗费的时间要比矩阵加(减)法耗费的 Strassen发现通过7次乘法运算: 时间多得多。要想改进矩阵乘法的计算时间复杂 性 须减少乘法运算 MAu(B1-B2 M2=(A1+A12)B 按照上述分治法的思想可以看出,要想减少乘 M3=(A21+A2)B 法运算次数,关键在于计算2个2阶方阵的乘积时 否用少于8次乘法运算。 Strassen提出了一种新的 算法来计算2个2阶方阵的乘积 M5=(A1+Az)(Bn+Bz M=(A12-Az)(B21+B2) 得到C1等值 效果 =M5+M4-M2+M6 C12=M1+M C21=M3+M4 T(n) O(1) C22=M5+M-M3-M7 77(m/2)+O(n)n>2 比速方的时向复H比含超闻 清华太学未证想 Strassen是如何发现的? 讨论 ■谁知道? 一种可能的方法:分析法 Hopcroft和Ker在1971年已经证明,计算个2×2矩阵 乘积,7次乘法是必要的 strassen之后又有许多算法改进了矩阵乘法的计算时间 8种基本元素A月1 复杂性。目前最好的计算时间上界是On2) ■有可能用少于8次乘法完成 实际使用很少,有4条理由 如何利用7次乘法计算【具体参见P736】? 1.阶数低系数大【 Cross point,不同情况下n=8 Dignam 12[ Huss-Lederman20实嗣,用试验方法】 2.稀疏矩阵有更好方法 3.数值稳定性不够 4.占用空间大2 清华大学 宋斌恒 7 这个递归方程的解仍然是T(n)= O(n3)。因此， 该方法并不比用原始定义直接计算更有效。究其原 因，乃是由于该方法并没有减少矩阵的乘法次数。 而矩阵乘法耗费的时间要比矩阵加（减）法耗费的 时间多得多。要想改进矩阵乘法的计算时间复杂 性，必须减少乘法运算。 按照上述分治法的思想可以看出，要想减少乘 法运算次数，关键在于计算2个2阶方阵的乘积时， 能否用少于8次乘法运算。Strassen提出了一种新的 算法来计算2个2阶方阵的乘积。 清华大学 宋斌恒 8 只用7次乘法运算 Strassen发现通过7次乘法运算： M1=A11(B12－B22) M2=(A11+A12) B22 M3=(A21+A22) B11 M4=A22(B21－B11) M5=(A11+A22) (B11+B22) M6=(A12 － A22) (B21+B22) M7=(A11－ A21) (B11+B12) 清华大学 宋斌恒 9 得到C11等值 C11＝M5＋M4－M2＋ M6 C12＝M1＋M2 C21＝M3＋M4 C22＝M5＋M1－M3－ M7 清华大学 宋斌恒 10 效果 Strassen矩阵乘法中，用了7次对于n/2阶矩阵乘的递归调 用和18次n/2阶矩阵的加减运算。由此可知，该算法所 需的计算时间T(n)满足如下的递归方程： 解此递归方程得T(n) =O(n log7) ≈ O(n2.81)。由此可 见，Strassen矩阵乘法的计算时间复杂性比普通矩阵 乘法有较大改进。 î í ì + > = = 7 ( / 2) ( ) 2 (1) 2 ( ) 2 T n O n n O n T n 清华大学 宋斌恒 11 Strassen是如何发现的？ n 谁知道？ n 一种可能的方法：分析法 n 4个式子 n 8种基本元素AijBij n 有可能用少于8次乘法完成 n 如何利用7次乘法计算【具体参见P736】？ 清华大学 宋斌恒 12 n Hopcroft和Kerr在1971年已经证明，计算2个 2 ×2矩阵 的乘积，7次乘法是必要的。 n Strassen之后又有许多算法改进了矩阵乘法的计算时间 复杂性。目前最好的计算时间上界是O(n2.376)。 n 实际使用很少，有4条理由 1. 阶数低系数大【Cross Point, 不同情况下n = 8[Hignam], 12[Huss-Lederman], 20[ 实际]，用试验方法】 2. 稀疏矩阵有更好方法 3. 数值稳定性不够 4. 占用空间大 讨论