4 LU Decomposition

There are many algorithms for computing the LU decomposition of the matrix A. All algorithms derive a matrix L and a matrix U that satisfy Equation 37. Most algorithms also permit L and U to occupy the same amount of space as A. This implies that either L or U is computed as a unit triangular matrix so that explicit storage is not required for its diagonal (which is all ones).

There are two basic approaches to arriving at an LU decomposition:

  • Simulate Gaussian elimination by using row operations to zero elements in A until an upper triangular matrix exists. Save the multipliers produced at each stage of the elimination procedure as L.

  • Use the definition of matrix multiplication to solve Equation 37 directly for the elements of L and U.

Discussions of the subject by Fox [5]Golub and van Van Loan [8]Duff et al. [4], and Press et al. [14] are complementary in many respects. Taken as a group, these works provide a good sense of perspective concerning the problem.

LU Factorization Topics