文档介绍：(完整word版)高斯-塞德尔迭代并行算法
(完整word版)高斯-塞德尔迭代并行算法
(完整word版)高斯-塞德尔迭代并行算法
高斯 -塞德尔迭代并行算法
在并行计算中，高斯
-塞德尔迭代采用与雅可比迭代相同的数据划分。对于高斯
-塞德尔
迭代，计算 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 在 p p 1 中被计算出并广播至其余的处理器之后，
p0 计算出下一轮
的新的 x0 ，这样逐次迭代下去，直至收敛为止。具体算法框架描述如下：
算法 1 求解线性方程组的高斯 -塞德尔迭代并行算法
输入：系数矩阵 An n ，常数向量 bn n ，ε，初始解向量 xn n
输出：解向量 xn n
Begin
对所有处理器 my_rank(my_rank=0, , p-1) 同时执行如下的算法 :
(1) for i=my_rank*m to (my_rank+1)*m-1 do
/* 所有处理器并行地对主对角元素右边的数据求和 */
() sum[i]=
()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 为新旧值之差小于
() iteration=0
/* iteration 为本处理器中新旧值之差小于

ε的 x 的分量个数
ε的 x 的分量个数

*/
*/
(完整word版)高