page 1  (25 pages) 2

SPLIB: A LIBRARY OF ITERATIVE METHODS FOR SPARSE LINEAR SYSTEMS

<_author_search_(randall bramley)>RANDALL BRAMLEY AND <_author_search_(xiaoge wang?)>XIAOGE WANG?
DEPARTMENT OF COMPUTER SCIENCE
INDIANA UNIVERSITY - BLOOMINGTON
December 18, 1995

1. Introduction. Sparse linear systems are the primary consumer of computer time for most scientific and engineering computer programs. Analyzing them and developing faster and more accurate solution methods for the types of linear systems encountered in practice is difficult, however. Part of the difficulty is because those systems often fail to satisfy the hypotheses commonly assumed for detailed mathematical analysis. Difficulty in experimental testing of methods occurs because virtually every application program uses a different data structure for storing the coefficient matrix of the linear system. Testing different iterative solvers within the source program generally requires writing and tuning the solvers for the particular data structure, and also requires fitting the solver into the memory management scheme used by the source program. In practice, this means major recoding effort for each solver and preconditioner tried.

Because of this, a different methodology for collaborative work with scientists has proven useful: first, sample linear systems are extracted from the application program and written out to a file. Then using data structure conversion routines (which usually require writing a small routine customized for the application), the linear system is converted to a predetermined standard format. Once this is done, dozens of different solution methods and preconditioners can be tested on the linear system, and these tests can be run on workstations independently of the scientist's program. However, this approach is limited by space available for storing such extracted linear systems. Furthermore, for nonlinear solvers small differences in the solution of the linear system can cause large differences in the solution trajectory that the nonlinear problem follows. This necessitates a second phase of testing: directly calling a package of linear solvers from the application code. Again, a routine for converting from the application's native data structure to the one required by the linear solver package is required, but this generally involves only a small amount of programming. Only when a good solution strategy has been found should the extensive work required to implement it efficiently within the source program be carried out. The iterative library should also be relatively parsimonious with storage, so that it can reasonably be used as a production solver for small to medium sized applications.

SPLIB is a library of sparse iterative solvers, with preconditioners, for rapid prototyping of solvers for nonsymmetric linear systems of equations. SPLIB was developed with the intent that it be useful for comparing iterative methods and preconditioners in

? WORK SUPPORTED BY NSF GRANTS CDA 93-03189, CDA 93-09746, AND ASC-9502292