算法18.8函数 Leftmoveonestep(a)的基本算法 (1)if(=0)then/*最左端的子块* (1.1)将所存的A的子块发送到同行最右端子块所在的处理器中 (1.2)接收其右邻处理器中发来的A的子块 end if (2)if(G=sqrt(p}-1)and(mod2=0)then/最右端子块处理器且块列号为偶数* (2.1)将所存的A的子块发送到其左邻处理器中 (2.2)接收其同行最左端子块所在的处理器发来的A的子块 end if (3)if(G=sqrt(p}-1)and(mod2≠0)then/最右端子块处理器且块列号为奇数* (3,1)将所存的A的子块在缓冲区buer中做备份 (3,2)接收其同行最左端子块所在的处理器发来的A的子块 (33)将在缓冲区 buffer中所存的A的子块发送到其左邻处理器中 end if (4)if(≠sqrt(p)-)and(md2=0)and(≠0)then/其余的偶数号处理器 (41)将所存的A的子块发送到其左邻处理器中 (42)接收其右邻处理器中发来的A的子块 end if (5)if(sqrt(p)}-1)and(mod2=1)and(≠0)then/*其余的奇数号处理器* (5.1)将所存的A的子块在缓冲区buer中做备份 (52)接收其右邻处理器中发来的A的子块 (53)将在缓冲区 buffer中所存的A的子块发送到其左邻处理器中 d if End 当算法执行在√x√P的二维网孔上时,若使用切通CT选路法算法187第2)步的循环 移位时间为2(3+1m"P,第(4)步的单步移位时间为2+1"、运算时间为n3/p。 所以在二维网孔上 Cannon乘法的并行运行时间为Tp=4(s+1yNp+n3/p MPI源程序请参见章末附录 15LU分解 从本小节起我们将对LU分解等矩阵分解的并行计算做一些简单讨论。在许多应用问题 的科学计算中,矩阵的LU分解是基本、常用的一种矩阵运算,它是求解线性方程组的基础, 尤其在解多个同系数阵的线性方程组时特别有用 1.5.1矩阵的LU分解及其串行算法 对于一个n阶非奇异方阵A=c],对A进行LU分解是求一个主对角元素全为1的下三 角方阵L=[与上三角方阵 使A=LU。设A的各阶主子行列式皆非零,U和L的元 素可由下面的递推式求出算法 18.8 函数 Leftmoveonestep(a)的基本算法 Begin (1)if (j=0) then /*最左端的子块*/ (1.1)将所存的 A 的子块发送到同行最右端子块所在的处理器中 (1.2)接收其右邻处理器中发来的 A 的子块 end if (2)if ((j = sqrt(p)-1) and (j mod 2 = 0)) then /*最右端子块处理器且块列号为偶数*/ (2.1)将所存的 A 的子块发送到其左邻处理器中 (2.2)接收其同行最左端子块所在的处理器发来的 A 的子块 end if (3)if ((j = sqrt(p)-1) and (j mod 2 ≠ 0)) then /*最右端子块处理器且块列号为奇数*/ (3.1)将所存的 A 的子块在缓冲区 buffer 中做备份 (3.2)接收其同行最左端子块所在的处理器发来的 A 的子块 (3.3)将在缓冲区 buffer 中所存的 A 的子块发送到其左邻处理器中 end if (4)if ((j ≠ sqrt(p)-1) and (j mod 2 = 0) and (j ≠ 0)) then /*其余的偶数号处理器*/ (4.1)将所存的 A 的子块发送到其左邻处理器中 (4.2)接收其右邻处理器中发来的 A 的子块 end if (5)if ((j ≠ sqrt(p)-1) and (j mod 2 = 1) and (j ≠ 0)) then /*其余的奇数号处理器*/ (5.1)将所存的 A 的子块在缓冲区 buffer 中做备份 (5.2)接收其右邻处理器中发来的 A 的子块 (5.3)将在缓冲区 buffer 中所存的 A 的子块发送到其左邻处理器中 end if End 当算法执行在 p  p 的二维网孔上时,若使用切通 CT 选路法,算法 18.7 第(2)步的循环 移位时间为 p p n 2(ts tw ) 2 + ,第(4)步的单步移位时间为 p p n 2(ts tw ) 2 + 、运算时间为 n3 / p 。 所以在二维网孔上 Cannon 乘法的并行运行时间为 p n p p n Tp 4(ts tw ) / 3 2 = + + 。 MPI 源程序请参见章末附录。 1.5 LU 分 解 从本小节起我们将对 LU 分解等矩阵分解的并行计算做一些简单讨论。在许多应用问题 的科学计算中，矩阵的 LU 分解是基本、常用的一种矩阵运算，它是求解线性方程组的基础， 尤其在解多个同系数阵的线性方程组时特别有用。 1.5.1 矩阵的 LU 分解及其串行算法 对于一个 n 阶非奇异方阵 A=[aij]，对 A 进行 LU 分解是求一个主对角元素全为 1 的下三 角方阵 L=[lij]与上三角方阵 U=[uij]，使 A=LU。设 A 的各阶主子行列式皆非零，U 和 L 的元 素可由下面的递推式求出：