1)分别用普通的二分治法和V.Strassen算法求下列两矩阵相乘1041015021103021×0121201301041150(2)比较两种算法实际的运算效率==分治法·大整数乘法==
时间: 2023-05-27 17:03:46 浏览: 185
普通的二分治法:
将1041 0150与0121 2013拆分成四个部分,如下:
A=10 41
B=01 21
C=50 21
D=01 13
则原矩阵相乘可表示为:
AB CD
EF GH
其中,EF=AB+CD,GH=BC+DA,例如EF可表示为:
EF=(10×01)×10^4+[(10×21)+(41×01)]×10^2+50×21=10426
以此类推,可以计算出整个矩阵相乘的结果。
V.Strassen算法:
按照V.Strassen算法,将两个矩阵分成四个大小相等的子矩阵,即A11、A12、A21、A22和B11、B12、B21、B22。按照以下公式计算新的矩阵P1至P7:
P1=(A11+A22)×(B11+B22)
P2=(A21+A22)×B11
P3=A11×(B12-B22)
P4=A22×(B21-B11)
P5=(A11+A12)×B22
P6=(A21-A11)×(B11+B12)
P7=(A12-A22)×(B21+B22)
最后,计算新的矩阵C11、C12、C21、C22,即:
C11=P1+P4-P5+P7
C12=P3+P5
C21=P2+P4
C22=P1-P2+P3+P6
将C11、C12、C21、C22组合成一个矩阵即为原矩阵的乘积。
比较两种算法实际的运算效率:
在本题中,两个矩阵都是4x2的小矩阵,因此采用普通的二分治法计算较为简单,而采用V.Strassen算法反而会增加计算的复杂度,不会比普通算法更快。但是,对于大型矩阵的乘法,V.Strassen算法可以在O(n^2.81)的时间复杂度内解决,速度比普通的二分治法更快。因此,在不同的情况下,不同的算法可能会有不同的运算效率。
阅读全文