id for d if /*回代过程* (2 )for i=0 to m-I do m[=0.0 (3)for i=m-I downto o de I downto o d if( my_ rank=)then/*主行所在的处理器 ()x{p小=(b[小-m{)at*p+ (i)将x{*p+广播到所有处理器中 (infor k=0 to i-I do /*计算有关x[p+的内积项并累加* sm[=sm+a[k+小*x[*p d fo else非主行所在的处理器 (iv)接收广播来的x{p门的值 (v)if(my rank>n)then for k=0 to i-1 do /*计算有关x*p的内积项并累加* sum k =sunk+ ak, i*p+]*xi p+il nd f (vif( my rank分)then for k=0 to i de /*计算有关x[请*p+的内积项并累加* sum[ k]=sum[k]+ a[k,i*p+]*x[i*p+ end if end if end for end for End 消去过程中,参与计算的行向量数在减少,同时参与计算的行向量长度也在减少。设第 次消去参与变换的行向量数为(m-),行向量长度为(ny),其中=+p/2若取一次乘法和加法 运算时间或一次除法运算时间为一个单位时间,则上述算法所需的计算时间为T1= "2(m)p(n-)=(3m2-pm+4m2y12,其间共有n行数据作为主行被广播,通信时间为n(t+ (n+1)hn)logp;回代过程中,由于0号处理器对对应项进行乘积求和的计算量最大,因此以0 号处理器为对象分析。由于0号处理器计算解向量x(O),x(p),…,x(m-1)*)的时间分别为 mp,(m-1)…p,因此其回代过程的计算时间为T2=mp(m+1)2,解向量x的n个元素被播送给 所有处理器的通信时间为n(t+1m)logp。若不考虑选主元的时间而仅考虑一般高斯消去法的计
end for end if end for end for /*回代过程*/ (2)for i=0 to m-1 do sum[i]=0.0 end for (3)for i= m-1 downto 0 do for j= p-1 downto 0 do if (my_rank=j) then /*主行所在的处理器*/ (i)x[i*p+j]=(b[i]-sum[i])/a[i,i*p+j] (ii)将 x[i*p+j]广播到所有处理器中 (iii)for k =0 to i-1 do /*计算有关 x[i*p+j]的内积项并累加*/ sum[k]=sum[k]+ a[k,i*p+j]* x[i*p+j] end for else /*非主行所在的处理器*/ (iv)接收广播来的 x[i*p+j]的值 (v)if (my_rank>j) then for k =0 to i-1 do /*计算有关 x[i*p+j]的内积项并累加*/ sum[k]=sum[k]+ a[k,i*p+j]* x[i*p+j] end for end if (vi)if (my_rank<j) then for k =0 to i do /*计算有关 x[i*p+j]的内积项并累加*/ sum[k]=sum[k]+ a[k,i*p+j]* x[i*p+j] end for end if end if end for end for End 消去过程中，参与计算的行向量数在减少，同时参与计算的行向量长度也在减少。设第 i次消去参与变换的行向量数为(m-i)，行向量长度为(n-v)，其中v=ip+p/2若取一次乘法和加法 运算时间或一次除法运算时间为一个单位时间，则上述算法所需的计算时间为T1= − = 1 0 m i (m-i)*p*(n-v)=(3n 2 -pn+4mn2 )/12，其间共有n行数据作为主行被广播，通信时间为n[(ts+ (n+1)tw) logp；回代过程中，由于0号处理器对对应项进行乘积求和的计算量最大，因此以0 号处理器为对象分析。由于0号处理器计算解向量x(0),x(p),…,x((m-1)*p)的时间分别为 mp,(m-1)p, …,p，因此其回代过程的计算时间为T2=mp(m+1)/2，解向量x的n个元素被播送给 所有处理器的通信时间为n(ts+tw)logp。若不考虑选主元的时间而仅考虑一般高斯消去法的计
算时间,则此并行计算时间为Tp=(3m2pn+4m212+mp(m+1)/2+ nogal{21+(n+2)] MPI源程序请参见章末附录。 12约当消去法解线性方程组 121约当消去及其串行算法 约当消去法( Jordan Elimination)是一种无回代过程的直接解法,它直接将系数矩阵A变 换为单位矩阵,经变换后的常数向量b即是方程组的解。这种消去法的基本过程与高斯消去 法相同,只是在消去过程中,不但将主对角线以下的元素消成0,而且将主对角线以上的元 素也同时消成0。一般约当消去法的计算过程是按k=1,2…n的顺序,逐次以第k行作为主 行进行消去,以消去第k列除主元素以外的所有元素a1kak,…ank。记A0=A,用约当消去 法由A出发通过变换得到方阵序列{A(},A={a],(k=0,12,,n),每次由A4到A 的过程分为三步 (=k+1 b()=b(k-1)/a (2) (1≤i≤n,i≠k,k<j≤n) (3)a4)=1,a)=0(1≤i≤n,i≠k) 若取一次乘法和加法运算时间或一次除法运算时间为一个单位时间,则由于在第i次 消去中,参与变换的行向量数为n,行向量长度为i,所以下述算法19.3的约当消去法的时 间复杂度为∑m=n2(n+1)/2=O(m) 算法193单处理器上约当消去法求解线性方程组的算法 输入:系数矩阵Anxn,常数向量bnx1 输出:解向量xn×1 (lfor i=l to n do shifI(O= (2)for k-l to n do (21)d=0 (2. 2)for i=k to n do if( ali]I >d) then d=a[ L,js,Fiend if endfor
算时间，则此并行计算时间为Tp= (3n 2 -pn+4mn2 )/12+mp (m+1)/2+nlogp[2ts+ (n+2)tw]。 MPI源程序请参见章末附录。 1.2 约当消去法解线性方程组 1.2.1 约当消去及其串行算法 约当消去法(Jordan Elimination)是一种无回代过程的直接解法，它直接将系数矩阵 A 变 换为单位矩阵，经变换后的常数向量 b 即是方程组的解。这种消去法的基本过程与高斯消去 法相同，只是在消去过程中，不但将主对角线以下的元素消成 0，而且将主对角线以上的元 素也同时消成 0。一般约当消去法的计算过程是按 k=1,2, …,n 的顺序，逐次以第 k 行作为主 行进行消去，以消去第 k 列除主元素以外的所有元素 a1k,a2k, …,ank。记 A (0)=A，用约当消去 法由 A (0)出发通过变换得到方阵序列{ A (k)}，A (k)=[aij (k)]，（k=0,1,2,…,n），每次由 A (k－1)到 A (k) 的过程分为三步： ⑴ / ( 1,..., ) ( ) ( 1) ( 1) a a a j k n k kk k kj k kj = = + − − ( ) ( 1) ( 1) / − − = k kk k k k bk b a ⑵ (1 , , ) ( ) ( 1) ( 1) ( ) a a a a i n i k k j n k kj k ik k ij k ij = − − − ( ) ( 1) ( 1) (k ) kj k k k i k bi b b a − − = − ⑶ 1, 0 (1 , ) ( ) ( ) a a i n i k k ik k kk = = 若取一次乘法和加法运算时间或一次除法运算时间为一个单位时间，则由于在第 i 次 消去中，参与变换的行向量数为 n，行向量长度为 i，所以下述算法 19.3 的约当消去法的时 间复杂度为 ( 1)/ 2 2 1 = + = ni n n n i =О(n 3 )。 算法 19.3 单处理器上约当消去法求解线性方程组的算法 输入：系数矩阵 An×n，常数向量 bn×1 输出：解向量 xn×1 Begin (1)for i=1 to n do shift(i)=i end for (2)for k=1 to n do (2.1) d=0 (2.2)for i=k to n do for j=k to n do if (│a[i,j] │>d) then d =│a[i,j] │, js=j, l=i end if end for endfor