Introduction

NSPCG is a computer package to solve large sparse systems of linear equations by iterative methods. The package uses various acceleration techniques, such as the conjugate gradient method, Chebyshev acceleration and various generalized conjugate gradient methods for nonsymmetric systems, in conjunction with various preconditioners (or, basic iterative methods). NSPCG was developed as part of the ITPACK project of the Center for Numerical Analysis at The University of Texas at Austin [14,15,16].

Some of the salient features of the package are as follows:

• Accelerators for the nonsymmetrizable case such as ORTHOMIN, GCR (Generalized Conjugate Residual), Lanczos, and Paige and Saunders' LSQR method are provided, as well as accelerators for the symmetrizable case such as conjugate gradient and Chebyshev acceleration.
• Basic preconditioners such as Jacobi, Incomplete LU Decomposition, Modified Incomplete LU Decomposition, Successive Overrelaxation, and Symmetric Successive Overrelaxation are included in the package. Furthermore, some of these preconditioners are available either as left-, right-, or two-sided preconditioners. (See Section 5 for additional details.)
• The package is modular. Any preconditioner may be used with any accelerator, except for SOR which is unaccelerated. Any preconditioner may be used with any of the allowable data storage formats, except for block preconditioners which are available only with the diagonal data structures.
• Several matrix storage schemes are available. The user may represent the matrix in one of several sparse matrix formats: primary storage (the same format used in the ELLPACK package [24] from Purdue University), symmetric diagonal storage, nonsymmetric diagonal storage, symmetric coordinate storage, or nonsymmetric coordinate storage.
• The package can be used in a matrix-free mode, in which the user supplies customized routines for performing matrix operations.
• The data structures have been chosen for efficiency on vector, or pipelined, computers. Many of the preconditioners have been vectorized to work efficiently on such computers as the Cyber 205, Cray 1, and Cray X-MP. It is expected that the package would perform well on the Hitachi, Fujitsu and NEC supercomputers.

One of the purposes for the development of the NSPCG package was to investigate the suitability of various basic iterative methods for vector computers. The degree of vectorization that is possible for a particular iterative method often depends on the underlying structure of the matrix, the data structure used for the matrix representation, the ordering used for the equations, and the vector computer being used. NSPCG allows several sparse matrix data structures suitable for matrices with regular or irregular structures. Also, various orderings can be given to the equations to enhance vectorization of the basic iterative method. Finally, the package has been written so that it can be installed on supercomputers with different vectorizing philosophies (e.g., memory-to-memory computations as with the Cyber 205 computer or register-to-register computations as with the Cray computers). Another purpose for the development of the NSPCG package was to provide a common modular structure for research on iterative methods. In addition to providing a large number of preconditioners and accelerators, the package has been constructed to facilitate the addition of new preconditioners and new acceleration schemes into the package. Thus, the package is an experimental research tool for evaluating certain aspects of iterative methods and can provide a guide for the construction of an iterative algorithm which is tailored to a specific problem. The code is not intended to be used in production situations, but it can provide information on

• the convergence or nonconvergence of an iterative method
• the number of iterations required for convergence
• the existence of a preconditioner (e.g., incomplete factorization preconditioners)
• the suitability of an approximate stopping test in reference to an idealized stopping test
• the effectiveness of certain adaptive procedures for selecting iterative parameters
• some vectorization techniques for various iterative kernels using certain data structures

This information can then be used in designing a production iterative code.