矩阵乘法(分治法)

《矩阵乘法(分治法)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法设计与分析实验报告实验名称：矩阵乘法（分冶法）一、问题陈述和分析:1.实验目的：掌握分总冶策略的基本思想以及用分冶法解决问题的一般技巧.运用编程工具，并运用分冶法来解决矩阵乘法问题；2.实验内容：设A和B是两个阶矩阵，求它们两的乘积矩阵C。这里，假设n是2的幕次方；3.实验要求：编制程序并对其时间复杂度和空间复杂度进行分析.二、模型拟制、算法设计和正确性证明:设A和B是两个n*n阶矩阵，求他们两的成绩矩阵C。这里假设n是2的慕次方;A和B是两个n*n的矩阵，他们的乘积C二AB也是一个n*n的矩阵，矩阵

2、C中的元素C[iJUJZA[i][k]B[k][j]定义为Cli][j]='J，则每计算一个CliJljJ，需要做n次乘法和n-1次加法。因此计算C的『个元素需要爪次乘法和£・『次加法。因此所需的时间复杂度是0(爪)。但是使用分治法可以改进算法的时间复杂度。这里，假设n是2的幕。将矩阵A,B,C中每一矩阵都分成4个大小相等的子矩阵，每个子矩阵是(n/2)*(n/2)的方阵。由此,可将方阵C=AB重写为*B11B12司C21C223A21A223B21B22®因此可得：Cll二A11B11+A12B21C1

3、2二A11B12+A12B22C21=A21B11+A22B22C22二A21B12+A22B22这样就将2个n阶矩阵的乘积变成计算8个n/2阶矩阵的乘积和4个n/2阶矩阵的加法。当n二1吋，2个1阶方阵的乘积可直接算出，只需要做一次乘法。当子矩阵阶n>l吋，为求两个子矩阵的乘积，可继续对两个子矩阵分块，直到子矩阵的阶为1。由此，便产生了分治降阶的递归算法。但是这个算法并没有降低算法的时间SZ杂度。由strassen矩阵乘法,M1=A11(B12-B22)M2=(A11+A12)B22M3=(A21+A2

4、2)BllM4=A22(B21-B11)M5=(A11+A22)(B11+B22)M6=(A12-A22)(B21+B22)M7=(A11-A21)(B11+B12)C11=M5+M4-M2+M6C12=M1+M2C21二M3+M4C22=M5+M1-M3-M7算法共进行7次举证乘法，算法效率得到降低主要数据的定义：intn；n是方阵A,B,C的阶int**A二new//矩阵A,B,C的定义，并为它们分配空间。这里A,B是用//于相乘的矩阵，C用于存放AB的结果int二newint*[n];int**C=

5、newint*[n];inti,j;for(i=0;i

6、21,int**A22)函数实现的功能是：将四个(n/2)*(n/2)的矩阵All,A12,A21,A22合并成一个n*n的矩阵Ao4.voidAdd(intn,int**A,int**B,int**C)函数的功能是：实现C=A+B,A,B,C都是n*n矩阵。3.voidMui(intn,int**A,int**B,int**M)函数的功能是：将n*n的矩阵A,B相乘，结果存放在n*n的矩阵M中。算法设计：整个算法的大致思想是:在函数Mui(intn,int**A,int**B,int**M)中先判断n的

7、值,若n==l,表示A,B,C均为一阶方阵。则M[0][0]=A[0][0]*B[0][0h否则，调用Divide(n,A,A11,A12,A21,A22);和Divide(n,B,Bll,B12,B21,B22);将A和B都分为四个(n/2)*(n/2)的子矩阵。然后递归调用Sub(n,B12,B22,Tl);T1=B12-B22Mui(n,A11,T1,M1);M1=A11(B12-B22)Add(n,AH,A12,T2);Mui(n,T2,B22,M2);M2=(A11+A12)B22Add(n,A

8、21,A22,T1);Mul(n,Tl,Bll,M3);M3=(A21+A22)B11Sub(n,B21,B11,T1);Mul(n,A22,T1,M4);M4=A22(B21-B11)Add(n,All,A22,T1);Add(n,Bll,B22,T2);Mui(n,Tl,T2,M5);M5=(A11+A22)(B11+B22)Sub(n,A12,A22,T1);Add(n,B21,B22,T2);Mui(n,Tl,T2,M