d fo (2)p=a 3) while(p≥E)do (1)t=x (i)s= (iiiforj=I to n do if(≠)then end for (v)if(x-t>)then p=x-tend if end for end while 122高斯塞德尔迭代并行算法 在并行计算中,高斯-塞德尔迭代采用与雅可比迭代相同的数据划分。对于高斯塞德尔 迭代,计算x的新值时,使用x+,…,x-1的旧值和xn…x的新值。计算过程中x与x0,…x:1 及x+1,…,xn1的新值会在不同的处理器中产生,因此可以考虑采用时间偏移的方法,使各 个处理器对新值计算的开始和结束时间产生一定的偏差。编号为 my rank的处理器一旦计 算出x( my rank×m≤i<( my rank+1)×m)的新值,就立即广播给其余处理器,以供各处理 器对x的其它分量计算有关x的乘积项并求和。当它计算完x的所有分量后,它还要接收其 它处理器发送的新的x分量,并对这些分量进行求和计算,为计算下一轮的x作准备。计算 开始时,所有处理器并行地对主对角元素右边的数据项进行求和,此时编号为0的处理器(简 称为Po)计算出x然后广播给其余处理器,其余所有的处理器用x0的新值和其对应项进行 求和计算,接着P计算出x,x2…当P完成对xm-1的计算和广播后,P1计算出xm,并广播给 其余处理器,其余所有的处理器用xm的新值求其对应项的乘积并作求和计算。然后P1计算 出xm+1,xm+2,…,当P1完成对xm1的计算和广播后,P2计算出x·m…,如此重复下去,直 至xn在P1中被计算出并广播至其余的处理器之后,P0计算出下一轮的新的x0,这样逐次 迭代下去,直至收敛为止。具体算法框架描述如下 算法20.4求解线性方程组的高斯塞德尔迭代并行算法 输入:系数矩阵Axn,常数向量bn×1,ε,初始解向量x×1 输出:解向量x×1 对所有处理器 my rank( my rank=0,…,p-1)同时执行如下的算法 (I)for i=my-rank m to(my-rank+1)m-I do /*所有处理器并行地对主对角元素右边的数据求和* (1.1)stm{d=0.0 (1.2)forj=i+l to n-l d sumi=sum(i+aixi(1)for i=1 to n do xi=0 end for (2)p=ε+1 (3)while (p ≥ ε) do for i=1 to n do (i) t = xi (ii) s=0 (iii)for j= 1 to n do if (j ≠ i) then s= s+ aij xj end if end for (iv) xi=(bi-s)/ aii (v) if (│xi-t│>p) then p=│xi-t│end if end for end while End 1.2.2 高斯-塞德尔迭代并行算法 在并行计算中，高斯-塞德尔迭代采用与雅可比迭代相同的数据划分。对于高斯-塞德尔 迭代，计算xi 的新值时，使用xi+1, …,xn-1 的旧值和x0, …,xi-1 的新值。计算过程中xi 与x0, …,xi-1 及 xi+1, …,xn-1 的新值会在不同的处理器中产生，因此可以考虑采用时间偏移的方法，使各 个处理器对新值计算的开始和结束时间产生一定的偏差。编号为 my_rank 的处理器一旦计 算出 xi(my_rank×m ≤ i < (my_rank+1)×m)的新值，就立即广播给其余处理器，以供各处理 器对 x 的其它分量计算有关 xi 的乘积项并求和。当它计算完 x 的所有分量后，它还要接收其 它处理器发送的新的 x 分量，并对这些分量进行求和计算，为计算下一轮的 xi 作准备。计算 开始时，所有处理器并行地对主对角元素右边的数据项进行求和，此时编号为 0 的处理器（简 称为 P0）计算出 x0,然后广播给其余处理器，其余所有的处理器用 x0 的新值和其对应项进行 求和计算,接着 P0 计算出 x1,x2, …,当 P0 完成对 xm-1 的计算和广播后，P1 计算出 xm，并广播给 其余处理器，其余所有的处理器用 xm 的新值求其对应项的乘积并作求和计算。然后 P1 计算 出 xm+1,xm+2, …,当 P1 完成对 x2*m-1 的计算和广播后，P2 计算出 x2*m …，如此重复下去，直 至 xn-1 在 Pp-1 中被计算出并广播至其余的处理器之后，P0 计算出下一轮的新的 x0，这样逐次 迭代下去，直至收敛为止。具体算法框架描述如下： 算法 20.4 求解线性方程组的高斯-塞德尔迭代并行算法 输入：系数矩阵 An×n，常数向量 b n×1，ε，初始解向量 xn×1 输出：解向量 xn×1 Begin 对所有处理器 my_rank(my_rank=0,…, p-1)同时执行如下的算法: (1)for i=my-rank* m to (my-rank+1)*m-1 do /*所有处理器并行地对主对角元素右边的数据求和*/ (1.1)sum[i]=0.0 (1.2)for j=i+1 to n-1 do sum[i]=sum[i]+a[i,j]*x[j]