ITPACK History

The 2C version of the ITPACK codes described here is the result of several years of research and development. The development of ITPACK began in the early 1970's when Professor Garrett Birkhoff suggested that general purpose software for solving linear systems should be developed for iterative methods as well as for direct methods. Initially, prototype programs were written based on preliminary iterative algorithms involving adaptive selection of parameters and automatic stopping procedures. These programs were tested on a large set of elliptic partial differential equations over domains compatible with the subroutine REGION() [8] which superimposed a square grid over the domain. These routines were designed for solving self-adjoint elliptic partial differential equations. Next a preliminary version of ITPACK was coded in standard FORTRAN. The ITPACK routines used iterative algorithms which were refined from the prototype programs. However, these routines were designed to solve large sparse linear systems of algebraic equations instead of partial differential equations. The use of three interchangeable symmetric sparse storage modes in ITPACK 1.0 [3] allowed for great flexibility and made it possible to solve a wider class of problems than the prototype programs and to study different storage modes for iterative methods. The next version, ITPACK 2.0 [4], was significantly faster than its predecessor since it was restricted to allow only one sparse symmetric storage format. Most of the iterative algorithms utilized in the 2.0 version of this package assume that the coefficient matrix of the linear system is symmetric positive definite. As with many packages, the need to handle a slightly larger class of problems, namely, nearly symmetric systems, soon became evident. This required adapting the routines to allow a switch for either a symmetric or nonsymmetric storage mode in ITPACK 2A [5]. Moreover, a modification of the Conjugate Gradient algorithms was developed to handle nearly symmetric systems [12]. ITPACK has been improved in the 2B version [14] by (a) writing more efficient versions of several key subroutines, (b) incorporating Basic Linear Algebra Subprograms, BLAS [15], and (c) improving the user interface with better printing and documentation. Some additional improvements and corrections were made in the 2C version. The algorithms in ITPACK are not guaranteed to converge for all linear systems but have been shown to work successfully for a large number of symmetric and nonsymmetric systems which arise from solving elliptic partial differential equations [1,13]. The numerical algorithms in ITPACK 2C correspond to those described in the appendix of technical report [5] and outlined in the book [7]. In particular, the SOR code is based on an algorithm suggested to us by L. Hageman. Various other algorithms exist for iterative methods. For example, S. Eisenstat has an implementation of the Symmetric Successive Overrelaxation preconditioned Conjugate Gradient procedure.¹⁰ Modules based on the seven iterative routines in ITPACK have been incorporated into the elliptic partial differential equation solving package ELLPACK [17] together with all the necessary translation routines needed. The user-oriented modules described in Section 4 are not in ELLPACK. Moreover, if the ELLPACK system is not being used to generate the linear system for ITPACK, it is recommended that ITPACK be used as a stand-alone package apart from ELLPACK.

Acknowledgements

The authors wish to thank the referee for carefully going through the code and documentation for several different versions. Test runs were made on a variety of computer systems and helpful suggestions were made by R. Boisvert, W. Coughran, J. Dongarra, W. Dyksen, S. Eisenstat, S. Fillebrown, P. Gaffney, W. Gordon, R. Hanson, R. Lynch, J. Rice, B. Ward, and others. These suggestions and comments together with those of the referee have resulted in an improved software package. ITPACK has been tested on the following computing machines: CDC 6400, 6500, 6600, 7600, Cyber 170/750, 203, 205; Cray 1; DEC 10, 20, PDP 10, VAX 11/750, 11/780; IBM 195, 370/158, 3033; PRIME 400, 750; and others.