矩阵-向量并行乘法算法

《矩阵-向量并行乘法算法》由会员分享，可在线阅读，更多相关《矩阵-向量并行乘法算法（5页珍藏版）》请在金锄头文库上搜索。

矩阵-向量并行乘法算法SC03011068 张秀清矩阵-向量乘法思想：矩阵-向量乘法是将一个n*n阶矩阵A=aij乘以n*1的向量 B=b1,b2,bnT，得到一个具有n个元素的列向量C=c1,c2,cnT。假设一次乘法和加法运算时间为一个单位时间，则矩阵向量乘法算法的时间复杂度是O(n2)。矩阵-向量乘法的串行算法：算法 单处理器上矩阵-向量乘算法输入：An*n,Bn*1输出：Cn*1Begin for i=0 to n-1 doci=0for j=0 to n-1 do ci=ci+ai,j*bjend forend for End矩阵-向量乘法的并行算法：矩阵-向量乘法同样可以有带状划分和棋盘划分两种并行算法，这里仅讨论行带划分矩阵-向量乘法，列带划分矩阵-向量乘法是类似的。设处理器，个数为，对矩阵按行划分为块，每块含有连续的行向量，这些行块依次记为，分别存放在标号为的处理器中，同时将向量广播给所有处理器。个处理器并行地对存于局部数组中的行块和向量做乘积操作，具体并行算法框架描述如下：矩阵-向量乘并行算法：算法 行带状划分的矩阵-向量乘并行算法输入: An*n,Bn*1输出: Cn*1Begin 对所有处理器同时执行如下的算法:for i=0 to m-1 doci=0.0for j=0 to n-1 do ci=ci+ai,j*bjend forend forEnd