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

882 HP MLIB User’s Guide
What you need to know to use these subprograms
process is recovered many times over by the reduction obtained in the cost of
the factorization. In some applications, it is common to have several unknowns
associated with each grid point of the solution domain. Sparse matrices derived
from these applications tend to have some special properties in their structure.
A technique known as compression can often improve the effectiveness of the
minimum degree reordering. This package provides an option to turn on
compression for these applications.
Optionally, users can turn on another ordering scheme based on the multilevel
nested dissection algorithm, developed by George Karypis and Vipin Kumar
from the University of Minnesota for the METIS package. The multilevel
nested dissection algorithm has been seen to be effective for certain
applications, such as matrices from linear programming (LP) problem and 3-D
finite element problems using brick elements. Refer to the dsleop(3m) man page
for details about selecting alternative reordering algorithms.
The numeric factorization algorithm processes columns with like structure
simultaneously. This processing yields higher efficiency than older sparse
matrix algorithms. The ordering is modified to collect columns of the
factorization which have identical structure. One way to achieve higher
computational rates at the cost of performing more numerical operations is to
relax the ordering so that more columns can be collected together for
simultaneous processing while allowing additional fill and hence more
floating-point operations. This package provides a relaxation parameter,
maxzer, which controls the amount of additional fill allowed for each set of
collected columns. If maxzer = 0 no additional fill is allowed. Do not use a larger
value without verifying that it actually improves performance.
Stability
This package is designed to solve three important classes of symmetric linear
systems. One class comprises systems where the coefficient matrix is positive
definite. Another class comprises the systems where the coefficient matrix is
indefinite, but nonsingular. (Negative definite matrices can be treated by the
positive definite subprograms by changing signs.) The third class comprises the
systems where the coefficient matrix is not symmetric, but has symmetric
structure.
The factorization PAP
T
= LDL
T
, with D diagonal, is always stable when A is
positive definite. This has the particular effect that the reordering phase can
choose any permutation P to maintain sparsity in the factor L. The
factorization of an indefinite coefficient matrix is not always stable. However, in
a manner closely related to LAPACK subprogram DSYTRF, a factorization can
always be computed by allowing the matrix D to be a block diagonal matrix,
where each block is either of size 1-by-1 or 2-by-2. It is also necessary to
incorporate a permutation for pivoting, based on the numerical progress of the
factorization, to create the proper 2-by-2 blocks that provides stability.