Approaches to LU decomposition which systematically capture the intermediate results of Gaussian elimination often differ in the order in which A is forced into upper triangular form. The most common alternatives are to eliminate the subdiagonal parts of A either one row at a time or one column at a time. The calculations required to zero a complete row or a complete column are referred to as one stage of the elimination process.
The effects of the kth stage of Gaussian elimination on the A matrix are summarized by the following equation.
The notation a means the value of aij produced during the kth stage of the elimination procedure. In Equation 27, the term (sometimes referred to as a multiplier) captures the crux of the elimination process. It describes the effect of eliminating element aik on the other entries in row i during the kth stage of the elimination. In fact, these multipliers are the elements of the lower triangular matrix L, i.e.
The algorithm overwrites aij with lij when i < j. Otherwise, aij is overwritten by uij. The algorithm creates a matrix U that is upper triangular and a matrix L that is unit lower triangular. Note that a working vector w of length n is required by the algorithm.