(il)a[,1 nd for (3)fori= n downto l do/采用全主元高斯消去法的回代过程 forj=汁+ I to n do l]=a[*x可 end for end for (4)for k-l to n do for F=l to n do if(shjl=k)then输出x{k]的值x{ i end if end fo end for 在全主元高斯消去法中,由于每次选择主元素的数据交换情况无法预计,因此我们不考 虑选主元的时间而仅考虑一般高斯消去法的计算时间复杂度。若取一次乘法和加法运算时间 或一次除法运算时间为一个单位时间,则消去过程的时间复杂度为22,回代过程的时间 复杂度为Σi,算法19.1的时间复杂度为(m3+3m2+2n)3=0m2 1912并行高斯消去算法 高斯消去法是利用主行i对其余各行j,>)作初等行变换,各行计算之间没有数据相 关关系,因此可以对矩阵A按行划分。考虑到在计算过程中处理器之间的负载均衡,对A 采用行交叉划分。设处理器个数为p矩阵A的阶数为n,m=「m/p,对矩阵A行交叉划分后, 编号为i(=0,1,…,p-1)的处理器含有A的第,计p,…+(m1)p行和向量B的第i, 计+p,…,计+(m-1)一共m个元素 消去过程的并行是依次以第0,1,…;n-1行作为主行进行消去计算,由于对行的交叉划分 与分布,这实际上是由各处理器轮流选出主行。在每次消去计算前,各处理器并行求其局部 存储器中右下角阶子阵的最大元。若以编号为 my rank的处理器的第i行作为主行,则编号 在 my rank后面的处理器(包括 my rank本身)求其局部存储器中第i行至第m1行元素的 最大元,并记录其行号、列号及所在处理器编号;编号在 my rank前面的处理器求其局部 存储器中第计+1行至第m-1行元素的最大元,并记录其行号、列号及所在处理器编号。然后 通过扩展收集操作将局部存储器中的最大元按处理器编号连接起来并广播给所有处理器,各 处理器以此求得整个矩阵右下角阶子阵的最大元 maxvalue及其所在行号、列号和处理器编 号。若 maxvalue的列号不是原主元素ak的列号,则交换第k列与 maxvalue所在列的两列 数据:若 maxvalue的处理器编号不是原主元素ak的处理器编号,则在处理器间的进行行交 换;若 maxvalue的处理器编号是原主元素ak的处理器编号,但行号不是原主元素ak的行 号,则在处理器内部进行行交换。在消去计算中,首先对主行元素作归一化操作ay=a/ak b=bk,然后将主行广播给所有处理器,各处理器利用接收到的主行元素对其部分行向量 做行变换。若以编号为 my rank的处理器的第i行作为主行,并将它播送给所有的处理器 则编号在 my_ rank前面的处理器(包括 my rank本身)利用主行对其第汁1…,m1行数据 和子向量B做行变换。编号在 my rank后面的处理器利用主行对其第i…,m1行数据和子向 量B做行变换(iii)a[i,k]=0 end for end for (3)for i=n downto 1 do /*采用全主元高斯消去法的回代过程*/ forj=i+1 to n do b[i]= a[i,j]* x[i] end for end for (4)for k=1 to n do for i=1 to n do if (shift[i]=k) then 输出 x[k]的值 x[i] end if end for end for End 在全主元高斯消去法中，由于每次选择主元素的数据交换情况无法预计，因此我们不考 虑选主元的时间而仅考虑一般高斯消去法的计算时间复杂度。若取一次乘法和加法运算时间 或一次除法运算时间为一个单位时间，则消去过程的时间复杂度为  = n i i 1 2 ，回代过程的时间 复杂度为  = n i i 1 ，算法 19.1 的时间复杂度为(n 3+3n 2+2n)/3=О(n 3 )。 19.1.2 并行高斯消去算法 高斯消去法是利用主行 i 对其余各行 j，(j>i)作初等行变换，各行计算之间没有数据相 关关系，因此可以对矩阵 A 按行划分。考虑到在计算过程中处理器之间的负载均衡，对 A 采用行交叉划分。设处理器个数为 p,矩阵 A 的阶数为 n，m = n / p ，对矩阵 A 行交叉划分后， 编号为 i(i=0,1,…, p -1)的处理器含有 A 的第 i, i+p,…,i+(m-1)p 行和向量 B 的第 i, i+p,…,i+(m-1)p 一共 m 个元素。 消去过程的并行是依次以第 0,1,…,n-1 行作为主行进行消去计算，由于对行的交叉划分 与分布，这实际上是由各处理器轮流选出主行。在每次消去计算前，各处理器并行求其局部 存储器中右下角阶子阵的最大元。若以编号为 my_rank 的处理器的第 i 行作为主行，则编号 在 my_rank 后面的处理器（包括 my_rank 本身）求其局部存储器中第 i 行至第 m-1 行元素的 最大元，并记录其行号、列号及所在处理器编号；编号在 my_rank 前面的处理器求其局部 存储器中第 i+1 行至第 m-1 行元素的最大元，并记录其行号、列号及所在处理器编号。然后 通过扩展收集操作将局部存储器中的最大元按处理器编号连接起来并广播给所有处理器，各 处理器以此求得整个矩阵右下角阶子阵的最大元 maxvalue 及其所在行号、列号和处理器编 号。若 maxvalue 的列号不是原主元素 akk的列号，则交换第 k 列与 maxvalue 所在列的两列 数据；若 maxvalue 的处理器编号不是原主元素 akk的处理器编号，则在处理器间的进行行交 换；若 maxvalue 的处理器编号是原主元素 akk的处理器编号，但行号不是原主元素 akk的行 号，则在处理器内部进行行交换。在消去计算中，首先对主行元素作归一化操作 akj=akj/akk , bk=bk/akk，然后将主行广播给所有处理器，各处理器利用接收到的主行元素对其部分行向量 做行变换。若以编号为 my_rank 的处理器的第 i 行作为主行，并将它播送给所有的处理器。 则编号在 my_rank 前面的处理器（包括 my_rank 本身）利用主行对其第 i+1,…, m-1 行数据 和子向量 B 做行变换。编号在 my_rank 后面的处理器利用主行对其第 i,…,m-1 行数据和子向 量 B 做行变换