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(10⁴) to O(10⁶) 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(n²) 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 Solvers

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(n²) 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 rates.

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 Solvers

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 performed on 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(10⁵) unknowns and O(10⁶-10⁷) 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.

bramley@cs.indiana.edu

Last updated: Tue Jan 26 12:31:05 1999