算时间,则此并行计算时间为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