logo资料库

并行计算大作业：矩阵乘法报告.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.12M 资料格式：docx 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    算法设计与分析实验报告 实验名称： 矩阵乘法(分冶法) 一、问题陈述和分析： 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 次举证乘法，算法效率得到降低 主要数据的定义： int n；n 是方阵 A,B,C 的阶 int **A=new int*[n]; //矩阵 A，B，C 的定义，并为它们分配空间。这里 A，B 是用 //于相乘的矩阵，C 用于存放 AB 的结果 int **B=new int*[n]; int **C=new int*[n]; int i,j; for(i=0;i
    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）满足如下递归方程   　　　　　　　　 ＝ n  2 (1) o 7 ( /2) T n 2 ( O n  ) 　　　ｎ＞２ 　　　　 解此递归方程得 ( T n O n ( )  log7 )  ( O n 2.81 ) ( T n O n ( )  log7 )  2.81 ( O n ) 。 由此可见，strassen 矩阵乘法的计算时间复杂性比普通乘法有较大改进。 空间复杂性： 程序中定义了一些整型变量和若干个二维数组。因此算法的时间复杂度是 O（n*n）。
    四、程序实现和测试过程： 程序测试过程（1） 测试过程（2）
    五、总结： 源程序： #include #include #include using namespace std; ifstream infile("123.txt",ios::in); void Input(int n,int **A) { //infile>>n; for(int i=0;i>A[i][j]; } void Output(int n,int **A) { for(int i=0;i
    } void Unit(int n,int **A,int **A11,int **A12,int **A21,int **A22) { int i,j; for(i=0;i
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料