next up previous contents
Next: Choleski Factorization Up: Direct Linear Solvers Previous: Direct Linear Solvers

LU Factorization

For a brief review, the sparse matrix A can be numerically factored into a lower triangular matrix L and an upper triangular matrix U as in equation 2, where all values on the diagonal of either L or U must equal 1 --- or . Equation 2 is solved by setting Ux=y, and substituting y for Ux. The numerical solution for Ly=b is found by forward reduction, and the numerical solution for x is calculated by backward substitution in the equation Ux=y. Triangular linear systems can be readily solved numerically by solving for the first value in the triangular linear system and substituting that value into subsequent equations. Additional discussions on the state of the literature for LU factorization are presented below.

Sparse LU factorization can mirror any similar dense factorization algorithm, although generally a sparse matrix algorithm has only one explicit for loop, which can be for any single index in the dense case. The remaining indices are examined only for non-zero values in the original matrix or for non-zero values that will occur from fillin in the matrix. Sparse matrix fillin occurs when a value that formally was zero becomes non-zero in the process of factoring the matrix. Fillin can be controlled in sparse factorization by ordering the matrix before performing the factorization if there is no requirement for pivoting to ensure numerical stability of the calculations [9]. There are many ordering techniques for position symmetric matrices, with one of the most common being minimum degree ordering. If pivoting is required to ensure numerical stability, a Markowitz ordering/pivoting strategy can be employed, and fillin determined during the solution of the matrix. The Markowitz ordering strategy selects pivots with the added constraint of minimizing fillin [9]. Additional discussions on the state of the literature for LU factorization are presented below.

As we continue the review of LU factorization, we present a general sequential sparse factorization algorithm, in figure 3, based upon the factorization algorithms commonly attributed to Doolittle for matrices that do not require pivoting. In Doolittle factorization, all values on the diagonal of L equal 1 --- . We also present general sequential sparse forward reduction and backward substitution algorithms in figures 4 and 5 respectively that would be used in conjunction with the Doolittle-based algorithm to solve for x in Ax=b.

 
Figure 3: Sparse LU Factorization - Doolittle Algorithm 

 
Figure 4: Sparse Forward Reduction for Doolittle Factorization 

 
Figure 5: Sparse Backward Substitution for Doolittle Factorization 



next up previous contents
Next: Choleski Factorization Up: Direct Linear Solvers Previous: Direct Linear Solvers



David P. Koester
Sun Oct 22 15:31:10 EDT 1995