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