矩阵乘法分治法.docx
- 文档编号:14086227
- 上传时间:2023-06-20
- 格式:DOCX
- 页数:13
- 大小:106.91KB
矩阵乘法分治法.docx
《矩阵乘法分治法.docx》由会员分享,可在线阅读,更多相关《矩阵乘法分治法.docx(13页珍藏版)》请在冰点文库上搜索。
矩阵乘法分治法
算法设计与分析实验报告
实验名称:
矩阵乘法(分冶法)
一、问题陈述和分析:
1.实验目的:
掌握分总冶策略的基本思想以及用分冶法解决问题的一般技巧.运用编程工具,并运用分冶法来解决矩阵乘法问题;
2.实验内容:
设A和B是两个n*n阶矩阵,求它们两的乘积矩阵C。
这里,假设n是2的幂次方;
3.实验要求:
编制程序并对其时间复杂度和空间复杂度进行分析.
二、模型拟制、算法设计和正确性证明:
设A和B是两个n*n阶矩阵,求他们两的成绩矩阵C。
这里假设n是2的幂次方;
A和B是两个n*n的矩阵,他们的乘积C=AB也是一个n*n的矩阵,矩阵C中的元素C[i][j]定义为C[i][j]=
,则每计算一个C[i][j],需要做n次乘法和n-1次加法。
因此计算C的n2个元素需要n3次乘法和n3-n2次加法。
因此,所需的时间复杂度是O(n3)。
但是使用分治法可以改进算法的时间复杂度。
这里,假设n是2的幂。
将矩阵A,B,C中每一矩阵都分成4个大小相等的子矩阵,每个子矩阵是(n/2)*(n/2)的方阵。
由此,可将方阵C=AB重写为
因此可得:
C11=A11B11+A12B21
C12=A11B12+A12B22
C21=A21B11+A22B22
C22=A21B12+A22B22
这样就将2个n阶矩阵的乘积变成计算8个n/2阶矩阵的乘积和4个n/2阶矩阵的加法。
当n=1时,2个1阶方阵的乘积可直接算出,只需要做一次乘法。
当子矩阵阶n>1时,为求两个子矩阵的乘积,可继续对两个子矩阵分块,直到子矩阵的阶为1。
由此,便产生了分治降阶的递归算法。
但是这个算法并没有降低算法的时间复杂度。
由strassen矩阵乘法,
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)
C11=M5+M4-M2+M6
C12=M1+M2
C21=M3+M4
C22=M5+M1-M3-M7
算法共进行7次举证乘法,算法效率得到降低
主要数据的定义:
intn;n是方阵A,B,C的阶
int**A=newint*[n];//矩阵A,B,C的定义,并为它们分配空间。
这里A,B是用//于相乘的矩阵,C用于存放AB的结果
int**B=newint*[n];
int**C=newint*[n];
inti,j;
for(i=0;i { A[i]=newint[n]; B[i]=newint[n]; C[i]=newint[n]; } 程序中定义的函数: 1.voidDivide(intn,int**A,int**A11,int**A12,int**A21,int**A22) 函数实现的功能是: 将n*n的矩阵A分块成四个大小相等的(n/2)*(n/2)的子矩阵A11,A12,A21,A22。 2.voidUnit(intn,int**A,int**A11,int**A12,int**A21,int**A22) 函数实现的功能是: 将四个(n/2)*(n/2)的矩阵A11,A12,A21,A22合并成一个n*n的矩阵A。 4.voidAdd(intn,int**A,int**B,int**C) 函数的功能是: 实现C=A+B,A,B,C都是n*n矩阵。 3.voidMul(intn,int**A,int**B,int**M) 函数的功能是: 将n*n的矩阵A,B相乘,结果存放在n*n的矩阵M中。 算法设计: 整个算法的大致思想是: 在函数Mul(intn,int**A,int**B,int**M)中先判断n的值,若n==1,表示A,B,C均为一阶方阵。 则M[0][0]=A[0][0]*B[0][0];否则,调用Divide(n,A,A11,A12,A21,A22);和Divide(n,B,B11,B12,B21,B22);将A和B都分为四个(n/2)*(n/2)的子矩阵。 然后递归调用 Sub(n,B12,B22,T1);T1=B12-B22 Mul(n,A11,T1,M1);M1=A11(B12-B22) Add(n,A11,A12,T2); Mul(n,T2,B22,M2);M2=(A11+A12)B22 Add(n,A21,A22,T1); Mul(n,T1,B11,M3);M3=(A21+A22)B11 Sub(n,B21,B11,T1); Mul(n,A22,T1,M4);M4=A22(B21-B11) Add(n,A11,A22,T1); Add(n,B11,B22,T2); Mul(n,T1,T2,M5);M5=(A11+A22)(B11+B22) Sub(n,A12,A22,T1); Add(n,B21,B22,T2); Mul(n,T1,T2,M6);M6=(A12-A22)(B21+B22) Sub(n,A11,A21,T1); Sub(n,B11,B12,T2); Mul(n,T1,T2,M7);M7=(A11-A21)(B11+B12) Add(n,M5,M4,T1); Sub(n,T1,M2,T2); Add(n,T2,M6,M11);M11=M5+M4-M2+M6 Add(n,M1,M2,M12);M12=M1+M2 Add(n,M3,M4,M21);M21=M3+M4 Add(n,M5,M1,T1); Sub(n,T1,M3,T2); Sub(n,T2,M7,M22);M22=M5+M1-M3-M7 Unit(n,M,M11,M12,M21,M22); 将上面得到的四个矩阵组合成一个n*n矩阵。 则这个n*n矩阵就是AB的结果C。 正确性证明: 由矩阵乘法的计算方法可知,上述计算方法显然正确 三、时间和空间复杂性分析: 时间复杂性: Strassen矩阵乘法中,用了7次对于n/2阶矩阵乘法的递归调用和18次n/2阶矩阵的加减运算。 由此可知,该算法所需的计算时间T(n)满足如下递归方程 解此递归方程得 。 由此可见,strassen矩阵乘法的计算时间复杂性比普通乘法有较大改进。 空间复杂性: 程序中定义了一些整型变量和若干个二维数组。 因此算法的时间复杂度是O(n*n)。 四、程序实现和测试过程: 程序测试过程 (1) 测试过程 (2) 五、总结: 源程序: #include #include #include usingnamespacestd; ifstreaminfile("123.txt",ios: : in); voidInput(intn,int**A) { //infile>>n;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 矩阵 乘法 分治
![提示](https://static.bingdoc.com/images/bang_tan.gif)