n,m=「n/pl,对矩阵A行交叉划分后,编号为=1,…p1)的处理器存有A的第,汁+p… 计+(m-1)行。然后依次以第0.,1,…;n-1行作为主行,将其广播给所有处理器,各处理器利用 主行对其部分行向量做行变换,这实际上是各处理器轮流选出主行并广播。若以编号为 my rank的处理器的第i行元素作为主行,并将它广播给所有处理器,则编号大于等于 my rank的处理器利用主行元素对其第计1,…,m1行数据做行变换,其它处理器利用主行元 素对其第讠…m-1行数据做行变换。具体并行算法框架描述如下 算法18.10矩阵LU分解的并行算法 输入:矩阵Anxn 输出:下三角矩阵Lnxn,上三角矩阵Unxn Begin 对所有处理器 my rank( my rank=0,…,p-l)同时执行如下的算法 for i=0 to m-I do (1)ir( my rank=)then/*当前处理的主行在本处理器* (1.1)叶j/*v为当前处理的主行号* (1.2 )for k-y to n de fk=a{k/*主行元素存到数组∫中* nd fo (1.3)向其它所有处理器广播主行元素 else/*当前处理的主行不在本处理器* (14)=p+ (1.5)接收主行所在处理器广播来的主行元素 (2if( my rank≤then (2. 1 )for k-i+l to m-l do (ia[k, v]=akk, vvI (iife I to n-l do a[k w]=a[k, wl]*a[k,vl end for or (2.2 )for k-i to m-I do (iak, v]=ak, v/fvl (iifor w=v+l to n-l do a[kv=a[kww]°akv or end fo 计算完成后,编号为0的处理器收集各处理器中的计算结果,并从经过初等行变换的矩 阵A中分离出下三角矩阵L和上三角矩阵U。若一次乘法和加法运算或一次除法运算时间 为一个单位时间,则计算时间为(n3-n)/3p;又n-1行数据依次作为主行被广播,通信时间为n，m = n/ p ，对矩阵 A 行交叉划分后，编号为 i(i=0,1,…,p-1)的处理器存有 A 的第 i, i+p,…, i+(m-1)p 行。然后依次以第 0,1,…,n-1 行作为主行，将其广播给所有处理器，各处理器利用 主行对其部分行向量做行变换，这实际上是各处理器轮流选出主行并广播。若以编号为 my_rank 的处理器的第 i 行元素作为主行，并将它广播给所有处理器，则编号大于等于 my_rank 的处理器利用主行元素对其第 i+1,…,m-1 行数据做行变换，其它处理器利用主行元 素对其第 i,…,m-1 行数据做行变换。具体并行算法框架描述如下： 算法 18.10 矩阵 LU 分解的并行算法 输入：矩阵 An×n 输出：下三角矩阵 Ln×n,上三角矩阵 Un×n Begin 对所有处理器 my_rank(my_rank=0,…,p-1)同时执行如下的算法: for i=0 to m-1 do for j=0 to p-1 do (1)if (my_rank=j) then /*当前处理的主行在本处理器*/ (1.1) v=i*p+j /* v 为当前处理的主行号*/ (1.2)for k=v to n do f[k]=a[i,k] /* 主行元素存到数组 f 中*/ end for (1.3)向其它所有处理器广播主行元素 else /*当前处理的主行不在本处理器*/ (1.4)v=i*p+j (1.5)接收主行所在处理器广播来的主行元素 end if (2)if (my_rank ≤ j) then (2.1)for k=i+1 to m-1 do (i)a[k,v]=a[k,v]/f[v] (ii)for w=v+1 to n-1 do a[k,w]=a[k,w]-f[w]*a[k,v] end for end for else (2.2)for k=i to m-1 do (i)a[k,v]=a[k,v]/f[v]; (ii)for w=v+1 to n-1 do a[k,w]=a[k,w]-f[w]*a[k,v] end for end for end if end for end for End 计算完成后，编号为 0 的处理器收集各处理器中的计算结果，并从经过初等行变换的矩 阵 A 中分离出下三角矩阵 L 和上三角矩阵 U。若一次乘法和加法运算或一次除法运算时间 为一个单位时间，则计算时间为(n 3 -n)/3p；又 n-1 行数据依次作为主行被广播，通信时间为