Overview of the Linear System Analyzer (LSA)
LSA Problem Domain
One of the most frequently encountered problems in
scientific computing is the manipulation and solution of large-scale,
sparse, unstructured systems of equations Ax = b. Here
large now means O(104)
to O(106) unknowns or more.
The term sparse means most of the entries in the matrix
are zeros. By storing only the nonzero terms, the memory
requirements are often reduced from O(n2)
to O(n), where n is the number of unknowns.
Here unstructured means the nonzeros in the
matrix do not follow a simple pattern, such as tridiagonal or
upper Hessenberg (see
http://www.ee.ic.ac.uk/hp/staff/dmb/matrix/ for a dictionary of
some of the matrix terminology used here).
In particular, this means the matrix is
nonsymmetric - which introduces severe robustness problems
for many solution methods.
Much research in the past thirty years has targeted solving
these systems, and several sophisticated techniques and codes are available.
Often these are classified as direct or iterative methods.
Direct methods perform a factorization such as Gaussian elimination
on the matrix A to get upper and lower triangular matrices
L and U . Then the system is solved using forward and backward
substitution on the vector b . Unfortunately,
fill-in can occur: entries that were originally zero in the
matrix A can be nonzero in the factors L and U .
In the worst case this can lead to O(n2) storage requirements,
clearly unacceptable for systems with n = 10 000 000 or more.
Direct methods handle this by applying reordering
methods, which permute the rows and/or columns of the matrix
A to reduce fill-in. Since pivoting in Gaussian elimination
implicitly permutes the rows of the matrix also, the benefits of
reordering can be undone during the factorization.
Strategies such as
Markovitz pivoting seek to balance pivoting for numerical
stability against retaining the original lower fill-in ordering.
Modern sparse direct solvers also are parameterized to allow efficient
block linear algebraic operations, to help achieve high computation
All of these techniques (reordering, Markovitz pivoting, blocking
parameterization) can lead to large differences in the numerical
quality of solution, amount of additional storage required, and
computational efficiency achieved. Choosing good settings for the
parameters involved requires experimentation and extensive testing.
Iterative methods use simple operations with the
matrix: two of the most common computational kernels are matrix-vector
multiplication (multiplying a vector d by A ), or
transpose matrix-vector multiplication.
A whole alphabet soup of iterative methods has been developed in
the past fifty years: BiCG, CGS, QMR, OrthoMin, GCR, etc.
Although the additional storage for iterative
methods typically is small (a few n-vectors), in all but the
simplest cases they don't work: convergence is slow or nonexistent
for problems coming from nontrivial applications.
Instead, the iterative method is applied to a preconditioned system
M-1Ax = M-1b,
where the matrix M, is a cheaply computed approximation to A.
Virtually all of the important research for applied iterative solvers
is in choosing a preconditioner. A typical one for general problems
is based on incomplete factorization: Gaussian elimination is
A, but entries outside a certain sparsity pattern or
below a cut-off numerical value are simply discarded during
the factorization. The approximate LU factors then define
the preconditioner M. In that sense, practical iterative solvers
are really hybrids between direct and iterative methods.
Iterative solvers also present a large parameter space to navigate:
solver method, preconditioner method, target sparsity patterns for
preconditioners, numerical cut-offs for numerical dropping,
stopping tests and tolerances, etc.
Furthermore, analyzing what has happened in the iterative solution
of a particular problem can be difficult.
Crafting a Solution Strategy
Choosing a solution strategy for solving large sparse linear systems
in realistic applications is still an art form. For every currently
existing solution method, an application area can be found which
gives linear systems that make the solver
fail by requiring too much memory or from nonconvergence.
Finding a solution strategy for an application still relies
heavily on experimentation and exploration.
Current Methodology for Developing Solution Strategies
A common approach for developing a solution strategy
is to "extract" the linear
system and write it to a file in some standard format.
Then the linear algebraist draws upon a collection of
programs for applying transformations on the linear system, which
read it in, perform manipulations, and then write it out to
another file. Other programs apply various solution
methods, reading in the linear system and writing out
summaries of the results of the computation such as
error estimates, memory usage, and time required. Control parameters
for these transformation and solver programs are typically from input
files, command line arguments, or a GUI. The linear algebraist tries
several combinations of these programs, comparing their results.
If a program runs only on a certain machine, the user can
either try to port it, or transfer a file with the linear system
to the remote machine and transfer the results back.
Applications now routinely generate and solve linear systems
with O(105) unknowns and
stored elements, requiring hundreds of Mbytes
of internal memory to represent. Unless the linear algebraist
is lucky and immediately finds a good combination of software
for the problem, much of the time gets spent in
file I/O and transfer.
For the applications user who tries to manage all of this
without expert help the situation is worse; much of the time
and effort is spent in recompiling code, trying to understand
adjustable parameters in the solution methods, and trying to
form a coherent picture of results from a variety of output
from the codes. The LSA is built to address these problems.
The Role of the LSA
The LSA is a
problem-solving environment for application scientists who wish to
quickly experiment with a variety of solution strategies and methods
for large sparse linear systems of equations, without having to integrate
large amounts of disparate code into their application. Once an effective
solution strategy is developed, the LSA can provide source code that can be
integrated into the user's application.
The LSA allows a user to
- Create a solution strategy without knowing the implementation
details of the computational routines.
- Navigate a potentially large parameter space quickly, with
expert advice supplied by the LSA when needed.
- Analyze and compare results from multiple solution strategies.
- Encapsulate a solution strategy as exportable Fortran/C code which
can then be incorporated into an application code.
Next page: Application components
in the LSA.
Last updated: Tue Jan 26 12:31:05 1999