End 132松弛法并行算法 松弛法并行算法和高斯-塞德尔迭代并行算法基本相同,只是在计算分量的时候,将对x 分量的新值的计算改为“x=(1-)*lemp+w*(b小-m)”,其中temp为功的原有值。 具体并行算法描述如下 算法20.6求解线性方程组的松弛迭代并行算法 输入:系数矩阵A2xn,常数向量bnx1,E,初始解向量xnx1 输出:解向量xn×1 对所有处理器 my rank( my rank=0,…,p-l)同时执行如下的算法 /*所有处理器并行地对主对角元素右边的数据求和 (1) for i=my-rank*m to(my-rank+ 1)*m-l do (1.1)sm{=0.0 (1.2)for=计+lton-ldo sm[=sm{小+a/*xU end for end for (2) while(toak<n)do/ total为新旧值之差小于c的x的分量个数* (2.1) iteration=0/ IteratIon为本处理器新旧值之差小于E的x的分量个数* (2.2)for户=0ton-1do/依次以第0,1,…,n-1行为主行* (i)if( my rank=q)then/*主行所在的处理器* x=(1-)*temp+n*b小]m)a*产生x的新的值* if(xlJ-temp<)then iteration= iteration +l end if 将x)的新值广播到其它所有处理器中 *对其余行计算x所对于的内积项并累加* for i=my-rank* m to( my-rank+1)*m-1 do if(≠then end if (i)else/其它处理器* 接收广播来的x]的新值 *对所存各行计算x所对于的内积项并累加* for i=my-rank* m to( my-rank+1)*m-1 do sm{=m{]+a[* nd fo end if (2.3)用 Allreduce操作求出所有处理器中 iteration值的和 total并广播到所有End 1.3.2 松弛法并行算法 松弛法并行算法和高斯-塞德尔迭代并行算法基本相同，只是在计算分量的时候，将对 x 分量的新值的计算改为“x[j]=(1-w)*temp+w* (b[j]- sum[j])/a[j,j]”，其中 temp 为 x[j]的原有值。 具体并行算法描述如下: 算法 20.6 求解线性方程组的松弛迭代并行算法 输入：系数矩阵 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] end for end for (2) while (total<n) do /*total 为新旧值之差小于 ε 的 x 的分量个数*/ (2.1) iteration=0 /* iteration 为本处理器新旧值之差小于 ε 的 x 的分量个数*/ (2.2) for j=0 to n-1 do /*依次以第 0,1, …, n-1 行为主行*/ (i) q=j/m (ii) if (my_rank=q) then /*主行所在的处理器*/ temp= x[j] x[j]=(1-w)*temp+w* (b[j]- sum[j])/a[j,j] /* 产生 x[j]的新的值*/ if (│x[j]-temp│<ε) then iteration= iteration +1 end if 将 x(j)的新值广播到其它所有处理器中 /*对其余行计算 x[j]所对于的内积项并累加*/ sum[j]=0 for i=my-rank* m to (my-rank+1)*m-1 do if (j ≠ i) then sum[i]=sum[i]+a[i,j]*x[j] end if end for (iii) else /*其它处理器*/ 接收广播来的 x[j]的新值 /*对所存各行计算 x[j]所对于的内积项并累加*/ for i=my-rank* m to (my-rank+1)* m-1 do sum[I]=sum[i]+a[i,j]*x[j] end for end if end for (2.3) 用 Allreduce 操作求出所有处理器中 iteration 值的和 total 并广播到所有