strassen矩阵乘法各种情况详细解答.ppt

Strassen矩阵乘法;一、n阶方阵的传统算法（蛮力法，教 材49页例3）;二、分治法的思想;;2）第二步：计算两个2阶方阵的乘积之后再合并。;如果用T(n)记两个n阶矩阵相乘所用的时间，则有如下递归关系式：; 综上所述可知：分治法的运用，方阵的乘法的算法效率并没有提高！该方法并不比用原始定义直接计算更有效。究其原因，是因为没有减少矩阵的乘法次数。;M1=A11(B12-B22) M2=(A11+A12)B22 M3=(A21+A22)B11 M4=A22(B21-B11);做了7次乘法后，再做若干次加、减法：　 C11=M5+M4-M2+M6 C12=M1+M2 C21=M3+M4 C22=M5+M1-M3-M7;直接推导可得：;由下图可以看出Strassen的算法与蛮力算法的差距。;五、具体算法;1.当n的值不是2k，但A，B是方阵时;2.当n的值不是2k，A，B也不是方阵时