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[1], Golub and Van Loan[2], Duff et al.[3], and  Press et al.[4] are complementary in many respects. Taken as a group, these works provide a good sense of perspective concerning the problem.