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.

By: Anshul Gupta

Published in: RC25076 in 2010


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .