lik i>k < 在计算过程中,首先计算出U的第一行元素,然后算出L的第一列元素,修改相应A 的元素;再算出U的第二行,L的第二列…,直至算出砌n为止。若一次乘法和加法运算或 次除法运算时间为一个单位时间,则下述LU分解的串行算法189时间复杂度为 (-1)i=(n3-n)/3=O(n) 算法189单处理器上矩阵LU分解串行算法 输入:矩阵 输出:下三角矩阵Lnxn,上三角矩阵Unxn Be (1 ) for k-l to n de (1. 1)for i=k+l to n do a[, k]=a[i, ka[k, k (1.2)for i=k+I to n do for户=k+ I to n do q=q[i小}[*ak nd fo (2 )for i=l to Mi=ali,j1 else u[iF=ali,j (22[i,i]=1 end for 152矩阵LU分解的并行算法 在LU分解的过程中,主要的计算是利用主行i对其余各行j,(>)作初等行变换,各行 计算之间没有数据相关关系,因此可以对矩阵A按行划分来实现并行计算。考虑到在计算 过程中处理器之间的负载均衡,对A采用行交叉划分:设处理器个数为p,矩阵A的阶数为aij (1)=aij aij (k+1)=aij (k) -likukj         =  = − a u i k i k i k l kk k ik ik ( ) 1 1 0       = a k j k j u k kj kj ( ) 0 在计算过程中，首先计算出 U 的第一行元素，然后算出 L 的第一列元素，修改相应 A 的元素；再算出 U 的第二行，L 的第二列…，直至算出 unn 为止。若一次乘法和加法运算或 一次除法运算时间为一个单位时间，则下述 LU 分解的串行算法 18.9 时间复杂度为 ( 1) ( ) / 3 3 1 i i n n n i  − = − = = O(n 3 )。 算法 18.9 单处理器上矩阵 LU 分解串行算法 输入：矩阵 An×n 输出：下三角矩阵 Ln×n,上三角矩阵 Un×n Begin (1)for k=1 to n do (1.1)for i=k+1 to n do a[i,k]=a[i,k]/a[k,k] end for (1.2)for i=k+1 to n do for j=k+1 to n do a[i,j]=a[i,j]-a[i,k]*a[k,j] end for end for end for (2)for i=1 to n do (2.1)for j=1 to n do if (j<i) then l[i,j]=a[i,j] else u[i,j]=a[i,j] end if end for (2.2)l[i,i]=1 end for End 1.5.2 矩阵 LU 分解的并行算法 在 LU 分解的过程中，主要的计算是利用主行 i 对其余各行 j，(j>i)作初等行变换，各行 计算之间没有数据相关关系，因此可以对矩阵 A 按行划分来实现并行计算。考虑到在计算 过程中处理器之间的负载均衡，对 A 采用行交叉划分：设处理器个数为 p，矩阵 A 的阶数为