Sparse Direct Methods

Direct methods for solving linear systems of the form are based on computing , where and are lower and upper triangular, respectively. Computing the triangular factors of the coefficient matrix is also known as decomposition. Following the factorization, the original system is trivially solved by
solving the triangular systems and . If is symmetric, then a factorization of the form is computed via Cholesky factorization, where is a lower triangular matrix (unit lower triangular in the case of factorization) and is a diagonal matrix. One set of common formulations of decomposition and Cholesky factorization for dense matrices are shown in Figures 1 and 2, respectively. Note that other mathematically equivalent formulations are possible by rearranging the loops in these algorithms. These algorithms must be adapted for sparse matrices, in which a large fraction of entries are zero. For example, if in the division step is zero, then this operation need not be performed. Similarly, the update steps can be avoided if either if is symmetric) is zero.

When is sparse, the triangular factors and typically have nonzero entries in many more locations than does. This phenomenon is known as fill-in, and results in a superlinear growth in the memory and time requirements of a direct method to solve a sparse system with respect to the size of the system. Despite a high memory requirement, direct methods are often used in many real applications due to their generality and robustness. In applications requiring solutions with respect to several right-hand side vectors and the same coefficient matrix, direct methods are often the solvers of choice because the one-time cost of factorization can be amortized over several inexpensive triangular solves.