HP MLIB User's Guide Vol. 2 7th Ed.

Chapter 13 Sparse Linear Equations 881
What you need to know to use these subprograms
Direct versus iterative solution
This package is a direct linear equation solver. That is, it computes an explicit
factorization of the matrix in a sparse analogy of the dense matrix subprograms
DSYTRF/DSYTRS and DPOTRF/DPOTRS in LAPACK. There are applications
where special, factorization-free algorithms can be used effectively. Algorithms
appropriate for these cases iterate toward a solution, improving an approximate
solution at each iteration.
Unfortunately, there is no generally effective iterative algorithm, only a
collection of algorithms each effective for particular classes of problems. Used
in the appropriate contexts, with only single or a few right-hand sides, and with
only limited accuracy required of the solutions, iterative algorithms can be
faster than direct methods. Used in the wrong contexts, iterative methods may
become inordinately expensive and inaccurate. In contrast, the subprograms
described here are designed to function well in general and, additionally,
represent the algorithm of choice for many classes of problems.
Fill and reordering
When the matrix A is symmetric, this package computes its LDL
T
factorization.
When the matrix is unsymmetric, the package computes the LU factorization of
A. It uses the factors to solve the system Ax=b. Here, L is a lower triangular
matrix, D is diagonal or quasi-diagonal, and U is an upper triangular matrix.
However, the sparsity of A is not sufficient to assure that L and U are sparse.
Indeed, L and U have nonzeros wherever A has nonzeros, but also has nonzeros
in other positions where A’s entries are zero. These additional entries are
known as fill. While fill is an intrinsic facet of the factorization process, the
amount of fill is often controllable—if P is a matrix representing a permutation
of the variables of the problem, the factorization of the matrix PAP
T
, can often
have significantly less fill than does the factorization of A, provided that the
permutation P is chosen appropriately.
For example, it has been common in solving sparse systems of small order to
choose permutations (to reorder the matrix) so that nonzero entries lie close to
the main diagonal and then to use subprograms from LAPACK for banded
matrices. Banded matrices are a special type of sparse matrix representation.
This package is based on more general sparse matrix principles, often resulting
in significantly less fill and correspondingly less work in computing the
factorization. The principle is the same in both approaches in that the matrix
must be reordered so that the factors are appropriately sparse. The reordering
process precedes the actual factorization. The package solves the problem
(PAP
T
)(Px)=(Pb). This transformation is invisible to the user.
The subprograms described in this chapter use a powerful heuristic, the
minimum degree algorithm, for choosing the reordering. This algorithm is
effective in general and is also efficient. In most cases, the cost of the reordering