4.3 Crout’s LU Factorization

An equivalent LU decomposition of A = LU may be obtained by assuming that L is lower triangular and U is unit upper triangular. This factorization scheme is referred to as Crout’s method. The defining equations for Crout’s method are

lij=aij-p=1i-1lipupj,whereijl_{ij}=a_{ij}-\displaystyle\sum_{p=1}^{i-1}l_{ip}u_{pj},\operatorname{where}i\geq j (33)

and

uij=aij-p=1i-1lipupjlii,wherei<ju_{ij}=\frac{a_{ij}-\displaystyle\sum_{p=1}^{i-1}l_{ip}u_{pj}}{l_{ii}},% \operatorname{where}i<j (34)

Algorithm 3 implements Crout’s method. Calculations are sequenced to compute one column of L followed by the corresponding row of U until A is exhausted.

Algorithm 3: Crout’s LU Decomposition
for j=1,,nj=1,\cdots,n
   for i=j,,ni=j,\cdots,n
      α=aij\alpha=a_{ij}
      for p=1,,j-1p=1,\cdots,j-1
         α=α-aipapj\alpha=\alpha-a_{ip}a_{pj}
      aij=αa_{ij}=\alpha
   for j=j+1,,nj=j+1,\cdots,n
      α=aij\alpha=a_{ij}
      for p=1,,i-1p=1,\cdots,i-1
         α=α-ajpapi\alpha=\alpha-a_{jp}a_{pi}
      aji=αajja_{ji}=\displaystyle\frac{\alpha}{a_{jj}}

Figure 2 depicts the computational sequence associated with Crout’s method.

Figure 2: Computational Sequence of Crout’s Method
The computational sequence for used to create a LU factorization (decomposition) of a matrix using Crout's method

You should observe that Crout’s method, like Doolittle’s, exhibits inner product accumulation.

A good comparison of the various compact factorization schemes is found in Duff et al. [4].