12矩阵向量乘法 121矩阵向量乘法及其串行算法 矩阵向量乘法 Matrix-Vector Multiplication)是将一个n×n阶方阵A=a]乘以n×1的向 量B={b,b2…,b]得到一个具有n个元素的列向量C=C,c,…c假设一次乘法和加法 运算时间为一个单位时间,则下述矩阵向量乘法算法83的时间复杂度为Omn3) 算法183单处理器上矩阵向量乘算法 输入:Anxn,Bnx 输出:Cn×1 for i=0 to n-l do c[=0 forj=0 to n-l do cFc+aibl end for end for 122矩阵向量乘法的并行算法 矩阵-向量乘法同样可以有带状划分( Striped Partitioning)和棋盘划分( Checker board Partitioning)两种并行算法。以下仅讨论行带状划分矩阵-向量乘法,列带状划分矩阵向量乘法 是类似的。设处理器个数为p,对矩阵A按行划分为p块,每块含有连续的m行向量, m=「n/p1,这些行块依次记为A,A,…,A1,分别存放在标号为0,1…p1的处理器中, 同时将向量B广播给所有处理器。各处理器并行地对存于局部数组a中的行块A和向量B 做乘积操作,具体并行算法框架描述如下: 算法184行带状划分的矩阵向量乘并行算法 输入:Anxn,Bnx1 输出:C nxI Be 对所有处理器 my rank( my rank=0,…,p-1)同时执行如下的算法 for i=0 to m-1 do c()=0.0 for户=0ton-ldo c{=c可+a[]*b end for end fe End 假设一次乘法和加法运算时间为一个单位时间,不难得出行带状划分的矩阵向量乘算 法184并行计算时间T=m2,若处理器个数和向量维数相当,则其时间复杂度为O(n) MPI源程序请参见所附光盘。1.2 矩阵-向量乘法 1.2.1 矩阵-向量乘法及其串行算法 矩阵-向量乘法(Matrix-Vector Multiplication)是将一个 n×n 阶方阵 A=[aij]乘以 n×1 的向 量 B=[b1,b2, …,bn] T得到一个具有 n 个元素的列向量 C=[c1,c2, …,cn] T。假设一次乘法和加法 运算时间为一个单位时间，则下述矩阵向量乘法算法 18.3 的时间复杂度为 O(n 2 )。 算法 18.3 单处理器上矩阵-向量乘算法 输入：An×n，Bn×1 输出：Cn×1 Begin for i=0 to n-1 do c[i]= 0 for j=0 to n-1 do c[i]=c[i] + a[i,j]*b[j] end for end for End 1.2.2 矩阵-向量乘法的并行算法 矩阵-向量乘法同样可以有带状划分(Striped Partitioning)和棋盘划分(Checker Board Partitioning)两种并行算法。以下仅讨论行带状划分矩阵-向量乘法,列带状划分矩阵-向量乘法 是类似的。设处理器个数为 p，对矩阵 A 按行划分为 p 块，每块含有连续的 m 行向量， m = n / p ，这些行块依次记为 A0, A1, …, Ap-1，分别存放在标号为 0,1,…,p-1 的处理器中， 同时将向量 B 广播给所有处理器。各处理器并行地对存于局部数组 a 中的行块 Ai 和向量 B 做乘积操作，具体并行算法框架描述如下： 算法 18.4 行带状划分的矩阵-向量乘并行算法 输入：An×n，Bn×1 输出：Cn×1 Begin 对所有处理器 my_rank(my_rank=0,…, p-1)同时执行如下的算法: for i=0 to m-1 do c(i)=0.0 for j=0 to n-1 do c[i] = c[i]+a[i,j]*b[j] end for end for End 假设一次乘法和加法运算时间为一个单位时间，不难得出行带状划分的矩阵-向量乘算 法 18.4 并行计算时间 Tp=n 2 /p，若处理器个数和向量维数相当，则其时间复杂度为 O(n)。 MPI 源程序请参见所附光盘