(1.3)b}=sm (2)max b[ (3)for i=2 to n d if( b(a >max)then max= b(i end if end fo (4)for i=I to n do x[=b/ end for (5)diff=max-oldmax, oldmaxmax end while 112乘幕法并行算法 乘幂法求矩阵特征值由反复进行矩阵向量相乘来实现,因而可以采用矩阵向量相乘的数 据划分方法。设处理器个数为p,对矩阵A按行划分为p块,每块含有连续的m行向量 这里m=「m/pl,编号为i的处理器含有A的第m至第(+1)m-1行数据,(=01,…P-1),初 始向量γ被广播给所有处理器 各处理器并行地对存于局部存储器中a的行块和向量ν做乘积操作,并求其m维结果 向量中的最大值 localmax,然后通过归约操作的求最大值运算得到整个n维结果向量中的最 大值max并广播给所有处理器,各处理器利用max进行规格化操作。最后通过扩展收集操 作将各处理器中的m维结果向量按处理器编号连接起来并广播给所有处理器,以进行下 次迭代计算,直至收敛。具体算法框架描述如下: 算法212乘幂法求解矩阵最大特征值的并行算法 输入:系数矩阵Amxn,初始向量νn×1,ε 输出:最大的特征值max Begin 对所有处理器 my rank( my rank=0,…,p-1)同时执行如下的算法 hil(dile)do/dif.特征向量的各个分量新旧值之差的最大值* (1)for=0tom-1do/*对所存的行计算特征向量的相应分量* (1.1)am=0 (1.2)forj=0 to n-l do sumsumtai, xlI end fo (1.3)6[}= end for (2) calmar=|b0]|/对所计算的特征向量的相应分量 求新旧值之差的最大值 locaImax+ ()for i=l to m-I do r( b[>localmax)then localmax b[a end if (4)用 Allreduce操作求出所有处理器中 locaImax值的最大值max 并广播到所有处理器中 (5)fori=0tom-1do/*对所计算的特征向量归一化*(1.3)b[i]= sum end for (2)max=│b[1]│ (3)for i=2 to n do if (│b[i]│>max) then max=│b[i]│ end if end for (4)for i=1 to n do x[i] =b[i]/max end for (5)diff=max-oldmax , oldmax=max end while End 1.1.2 乘幂法并行算法 乘幂法求矩阵特征值由反复进行矩阵向量相乘来实现，因而可以采用矩阵向量相乘的数 据划分方法。设处理器个数为 p，对矩阵 A 按行划分为 p 块，每块含有连续的 m 行向量， 这里 m = n/ p ，编号为 i 的处理器含有 A 的第 im 至第(i+1)m-1 行数据，(i=0,1, …,p-1)，初 始向量 v 被广播给所有处理器。 各处理器并行地对存于局部存储器中 a 的行块和向量 v 做乘积操作，并求其 m 维结果 向量中的最大值 localmax，然后通过归约操作的求最大值运算得到整个 n 维结果向量中的最 大值 max 并广播给所有处理器，各处理器利用 max 进行规格化操作。最后通过扩展收集操 作将各处理器中的 m 维结果向量按处理器编号连接起来并广播给所有处理器，以进行下一 次迭代计算，直至收敛。具体算法框架描述如下： 算法 21.2 乘幂法求解矩阵最大特征值的并行算法 输入：系数矩阵 An×n，初始向量 v n×1，ε 输出：最大的特征值 max Begin 对所有处理器 my_rank(my_rank=0,…, p-1)同时执行如下的算法: while (│diff│>ε) do /* diff 为特征向量的各个分量新旧值之差的最大值*/ (1)for i=0 to m-1 do /*对所存的行计算特征向量的相应分量*/ (1.1)sum=0 (1.2)for j= 0 to n-1 do sum=sum+a[i,j]*x[j] end for (1.3)b[i]= sum end for (2)localmax=│b[0]│ /*对所计算的特征向量的相应分量 求新旧值之差的最大值 localmax */ (3)for i=1 to m-1 do if (│b[i]│>localmax) then localmax=│b[i]│ end if end for (4)用 Allreduce 操作求出所有处理器中 localmax 值的最大值 max 并广播到所有处理器中 (5)for i=0to m-1 do /*对所计算的特征向量归一化 */