# 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 21. 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 21 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.