×

An introduction to the NSPCG software package. (English) Zbl 0719.68011

Summary: NSPCG is the most recent research-oriented software package developed as part of the ITPACK Project at the Center for Numerical Analysis of The University of Texas at Austin. It is designed to solve large sparse systems of linear equations by a variety of different non-symmetric preconditioned conjugate gradient methods. Several different sparse data storage schemes are available for storing the coefficient matrix of the linear system. Matrices with a wide range of structures from highly structured to completely unstructured can be accommodated. To limit memory requirements, the accelerators in the package can be called directly with the matrix stored in a user-defined sparse data storage format (for example, from a particular application) by supplying some user-written routines for certain matrix-vector operations. The main entry point into the package is through a single subroutine call. The various methods are accessed by using a particular naming convention for the first two parameters that in turn selects a preconditioner, an accelerator and a data storage scheme. Some of the basic preconditioners that are available are Jacobi, incomplete LU decomposition and symmetric successive overrelaxation as well as block preconditioners. The user can select from a large collection of accelerators such as conjugate gradient (CG), Chebyshev (SI, for semi-iterative), generalized minimal residual (GMRES), Biconjugate Gradient Squared (BCGS) and many others. The package is modular so that almost any accelerator can be used with almost any preconditioner. One of the main purposes for the development of the package was to provide a common modular structure for research on iterative methods. The entire package is written in Fortran 77 with vectorization in mind for applications on supercomputers.

MSC:

68N15 Theory of programming languages
65F50 Computational methods for sparse matrices
65F05 Direct numerical methods for linear systems and matrix inversion
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] ’Iterative algorithms for large sparse linear systems on parallel computers’. Doctoral Dissertation. University of Virginia, 1982. Also published as NASA CR-166027, NASA Langley Research Center.
[2] ’Incomplete block matrix factorization preconditioning methods. The ultimate answer?’. Report CNA-195, Center for Numerical Analysis, Univeristy of Texas, Austin, Texas, 1984.
[3] ’A survey of vectorizable preconditioning methods for large scale finite element matrix problems’, Report CNA-190, Center for Numerical Analysis, University of Texas, Austin, Texas, 1984. · Zbl 0552.65019
[4] and , Numerical Solution of Elliptic Problems, SIAM, Philadelphia, 1984. · doi:10.1137/1.9781611970869
[5] and , ’A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations’, in and (eds.), Sparse Matrix Computations, Academic Press, New York, 1976.
[6] Dongarra, Acm Trans. Math. Software 10 pp 219– (1984)
[7] Eisenstat, Siam J. Numer. Anal. 20 pp 345– (1983)
[8] in (ed.), Proc. Conf. on Numerical Analysis, Dundee, 1975 (Lecture Notes in Mathematics No. 506), Springer-Verlag, New York, 1976.
[9] Fridman, Ussr Comp. Math. Math. Phys. 2 pp 362– (1963)
[10] Dubois, Computing 362 (1979)
[11] and , ’ITPACK 2.0 user’s guide’, Report CNA-150, Center for Numerical Analysis, University of Texas at Austin, Austin. Texas, 1979.
[12] , and , ’ITPACK Report: Adaptive iterative algorithms using symmetric sparse storage’, Report CNA-139, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1978.
[13] ’Stability and rate of convergence of modified incomplete Cholesky factorization methods’, Doctoral Dissertation. Chalmers University of Technology and the University of Göteborg, 1979.
[14] and , Applied Iterative Methods, Academic Press, New York, 1981. · Zbl 0459.65014
[15] Jea, Linear Algebra Applic. 52/53 pp 399– (1983) · Zbl 0535.65018 · doi:10.1016/0024-3795(83)80026-3
[16] Johnson, Siam J. Numer. Anal. 20 pp 362– (1983)
[17] Joly, In J. Comp. Phys.
[18] Kershaw, J. Comp. Phys. 26 pp 43–
[19] and , ’ITPACK Report: Numerical studies of several adaptive iterative algorithms’, Report CNA-126, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1977.
[20] and , ’ITPACK on supercomputers’, in and (eds.), Numerical Methods (Lecture Notes in Mathematics 1005), Springer-Verlag, New York, 1983, pp. 151-161. (Also, Report CNA-178, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1982.)
[21] and , ’The development of a computer package for solving a class of partial differential equations by iterative methods’, Report CNA-102, Center for Numericl Analysis, University of Texas at Austin, Austin, Texas, 1975. (Also in Annales Association Internationale Calcul Analogique, 3, 186-191 (1975)). · Zbl 0307.65073
[22] and , ’Survey of iterative methods’, in et al. (eds.), Encyclopedia of Computer Sciences and Technology 13, Marcel Dekker, New York, 1979, pp. 354-391.
[23] and , ’The ITPACK project: Past, present, and future’, Report CNA-180, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1983. (Also in and eds.), Elliptic Problem Solvers II, Academic Press, New York, pp. 53-63, 1984.) · doi:10.1016/B978-0-12-100560-3.50010-X
[24] and , ’ITPACK–Adaptive iterative algorithms using symmetric sparse storage’, in Symposium on Reservoir Simulation, Society of Petroleum Engineers of AIME, Dallas, Texas, 1979, pp. 151-160.
[25] and , ’Vector computations for sparse linear systems’, Report CNA-189, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1984.
[26] Kincaid, Siam J. Alg. Disc. Math. 7 pp 99– (1986)
[27] Kincaid, Commun. Appl. Numer. Methods 2 pp 289– (1986)
[28] , and , ’ITPACKV 2C user’s guide’, Report CNA-191, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1984.
[29] , and , ’ITPACK solution modules’, Chapter 7 in and (eds.), Solving Elliptic Problems Using ELLPACK, Springer-Verlag, New York, 1985, pp. 237-258. · doi:10.1007/978-1-4612-5018-0_7
[30] Kincaid, Acm Trans. Math. Software 8 pp 302– (1982)
[31] Lawson, Acm Trans. Math. Software 5 pp 308– (1979)
[32] ’Adaptive iterative algorithms for large sparse linear systems’, Report CNA-203, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1986.
[33] and , ’ITPACK 3B user’s guide (preliminary version)’, Report CNA-201, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1986.
[34] Manteuffel, Math. Comp. 34 pp 473– (1980)
[35] Meijerink, Math. Comp. 31 pp 148– (1977)
[36] Oppe, Commun. Appl. Numer. Methods 3 pp 23– (1987)
[37] and , ’NSPCG user’s guide, version 1.0, a package for solving large sparse linear systems by various iterative methods’, Report CNA-216, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1988.
[38] Paige, Siam J. Numer. Anal. 12 pp 617– (1975)
[39] Paige, Acm Trans. Math. Software 8 pp 43– (1982)
[40] PCGPAK User’s Guide (Version 1.2). Scientific Computing Associates, New Haven, Connecticut, 1984.
[41] and (eds.), Solving Elliptic Problems Using ELLPACK. Springer-Verlag, New York, 1985. · Zbl 0562.65064 · doi:10.1007/978-1-4612-5018-0
[42] Saad, Math. Comp. 37 pp 105– (1981)
[43] Saad, Si Am J. Scientific Statistical Comp. 5 pp 203– (1984)
[44] Saad, Math. Comp. 44 pp 417– (1985)
[45] Saad, Si Am J. Scientific Statistical Comp. 7 pp 856– (1986)
[46] Sonneveld, Si Am J. Sci. Stat. Comp. 10 pp 36– (1989)
[47] Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, N. J., 1962.
[48] Iterative Solution of Elliptic Systems and Applications to the Neutron Diffusion Equations of Reactor Physics, Prentice-Hall, Englewood Cliffs, N. J., 1966. · Zbl 0161.12203
[49] ’Incomplete Gaussian elimination as a preconditioning for generalized conjugate gradient acceleration’, SPE SPE 12265, 1983, pp. 325-334.
[50] and , ’Constrained residual acceleration of conjugate residual methods’, SPE SPE 13536. 1985, pp. 415-428.
[51] Saunders, Si Am J. Numer. Anal. 25 pp 927– (1988)
[52] Iterative Solution of Large Linear Systems, Academic Press, New York, 1971.
[53] ’A historical review of iterative methods’, Report CNA-206, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1987. (To appear in Proceedings of the Conference on the History of Scientific and Numeric Computing, sponsored by the Association for Computing Machinery, Princeton, May 13-15, 1987.)
[54] Young, Linear Algebra Applic. 34 pp 159– (1980)
[55] and , ’The ITPACK package for large sparse linear systems’, Report CNA-160, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1980. (Also in (ed.), Elliptic Problem Solvers, Academic Press, New York, pp. 163-185, 1981.) · doi:10.1016/B978-0-12-632620-8.50013-9
[56] and , ’ITPACK 3A user’s guide (preliminary version)’, Report CNA-197, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1984.
[57] Young, Commun. Appl. Numer. Methods 4 pp 435– (1988)
[58] and , ’Preconditioned conjugate algorithms and software for solving large sparse linear systems’, Report CNA-207, Center for Numerical Analysis, University of Texas at Austin, Austin, Texas, 1987. (To appear in Proceedings of the SI AM Conference on Linear Algebra, Signals, and Control. Boston, Mass., Aug., (1986.)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.