高斯-塞德尔迭代并行算法

《高斯-塞德尔迭代并行算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、高斯•塞德尔迭代并行算法在并行计算中，高斯-塞徳尔迭代采用与雅可比迭代相同的数据划分。对于高斯-塞徳尔迭代，计算兀•的新值时，使用石+1，...,£_1的旧值和兀(),...,斥一]的新值。计算过程中兀与心…，心]及也，・..，£_]的新值会在不同的处理器中产生，因此可以考虑采用时间偏移的方法，使各个处理器对新值计算的开始和结束吋I'可产生一定的偏差。编号为my_rank的处理器一旦计算出x^my_rankxm

2、理器发送的新的无分量，并对这些分量进行求和计算，为计算下一-轮的壬作准备。计算开始时，所有处理器并行地对主对角元素右边的数据项进行求和，此时编号为0的处理器(简称为几)计算出勺，然后广播给其余处理器，其余所有的处理器用兀°的新值和其对应项进行求和计算，接着几计算出西,兀2，・・・，当Po完成对的计算和广播后，P计算出心，并广播给其余处理器，其余所有的处理器用色的新值求其对应项的乘积并作求和计算。然后卩]计算出兀,”+1，兀“+2,…，当P完成对兀2Z的计算和广播后,P2计算出兀2叽.'如此重复下去，直至兀门在中被计算出并广播至其余的处理器之后，几计算出下一轮的新的X

3、。，这样逐次迭代下去，直至收敛为止。具体算法框架描述如下：算法1求解线性方程组的高斯-塞徳尔迭代并行算法输入：系数矩阵常数向量仇X”，£，初始解向量暫“输出：解向量兀呦Begin对•所有处理器my_rank(my」ank二0,…，p-1)同时执行如下的算法：(1)fori=my_rank*mto(my_rank+l)*m-ldo/*所有处理器并行地对主对角元素右边的数据求和*/(1.1)sum[i]=0.0(1.2)forj=i+lton-1dosum[i]=sum[i]=4-a[ij]*x[j]endforendfor⑵while(total

4、新旧值之差小于£的x的分量个数*/(2.1)iteration=0/*iteration为本处理器屮新旧值Z差小于£的只的分量个数*/(1.2)forj=0ton-1do/*依次以第0,1,•••»n-1行为主行*/(i)q=j/m(ii)ifmy_rank=qthen/*主行所在的处理器*/temp=x[j],x[j]=(b[j]-sum[j])/a[j,j]/*产生x(j)的新的值*/if(

5、x[j]—temp

6、<£)theniteration=iteration+1endif将x[j]的新值广播到英它所有处理器中/*对其余行计算x[j]所对于的内积项并累加*/su

7、m[j]=0fori=my-rank*mto(my-rank+1)*m-ldoif(jHi)thensum[i]=sum[i]+a[ij]*x[j]endifendforelse/*其它处理器*/接收广播来的x[j]的新值/*对所存各行计算x[j]所对于的内积项并累加勺fori=my-rank*mto(my-rank+1)*m-1dosum[i]=sum[i]+a[i,j]*x[j]endforendifendfor(1.3)用Allreduce操作求出所有处理器屮iteration值的和total并广播到所有处理器中endwhileend若取一次乘法和加法运算时间或一

8、次比较运算时间为一个单位时间。在算法开始阶段，各处理器并行计算主对角线右边元素相应的乘积项并求和，所需时间mn-(l+m)m/2,进入迭代计算后，虽然各个处理器所负责的x的分量在每一轮计算中的开始时间是不一样的，但一轮迭代中的计算量都是相等的，因此不妨取0号处理器为对象分析一轮迭代计算的时间,容易得出0号处理器计算时间为mn+m；另外它在一轮迭代屮做广播操作n次，通信量为1,归约操作1次，通信量为1,所有的通信时间为n(ts+tw)logp+2ts(J万-1)+tw(p-1),因此高斯■塞徳尔迭代的一轮并行计算时间为Tp=mn+m+n(ts+log〃+2ts(Jp-1)

9、4-tw(P一1)。源程序如下：1.源程序seidel.c#includeustdio.hH#includeHstdlib.hH#include"mpi.h"#include"math.h"#defineE0.0001#definea(x,y)a[x*size+yl#defineb(x)b[x]#definev(x)v[x]/*A为size^size的系数矩阵*/#defineA(x,y)A[x*size+y]#defineB(x)B[x]#defineV(x)V[x]#defineintsizesizeof(int)#defineflo