We restructure three outstanding iterative methods for large sparse nonsymmetric linear systems. These methods are CGS (conjugate gradient squared), CRS (conjugate residual squared), and Orthomin(k). The re structured methods are more suitable for vector and parallel processing. We implemented these methods on a parallel vector system. The linear systems for the nu merical tests are obtained from discretizing four two- dimensional elliptic partial differential equations by finite difference and finite element methods. A vectorizable and parallelizable version of incomplete LU precondi tioning is used. We restructured the subroutines to en hance the data locality in vector machines with storage hierarchy. Speedup was measured for multitasking by four processors.
Get full access to this article
View all access options for this article.
References
1.
Chronopoulos, A., and Ma, S.1989. On squaring Krylov subspace iterative methods for nonsymmetric linear systems. TR 89-67. Minneapolis: University of Minnesota, Computer Science Department.
2.
Chronopoulos, A., and Gear, C.1989a. S-step iterative methods for symmetric linear systems. J. . Comput. Appl. Math.25:153-168.
3.
Chronopoulos, A., and Gear, C.1989b. On the efficient implementation of preconditioned s-step conjugate gradient methods on multiprocessors with memory hierarchy . Parallel Comput.11:37-53.
4.
Concus, P., and Golub, G.1976. A generalized conjugate gradient method for unsymmetric systems of linear equations. Lecture Notes in Econom. and Math. systems 139:56-65.
5.
Eisenstat, S.1981. Efficient implementation of a class of preconditioned conjugate gradient methods. SIAM J. Sci. Statist. Comput.2:1-4.
6.
Eisenstat, S., Elman, H., and Schultz, M.1983. Variational iterative methods for nonsymmetric systems of linear equations. SIAM J. Numer. Anal.20:345-357.
7.
Elman, H.1982. Iterative methods for large, sparse, nonsymmetric systems of linear equations. Ph.D. thesis, Yale University, Department of Computer Science.
8.
Filippone, S., and Radicati di Brozolo, G.1988. Vectorized ILU preconditioners for general sparsity patterns. Technical report. IBM ECSEC , Italy.
9.
Fletcher, R.1976. Conjugate gradient methods for indefinite systems . Lecture Notes in Math. 506:73-89.
10.
Johnson, C.1987. Numerical solutions of partial differential equations by the finite element method. Cambridge, U.K.: Cambridge University Press.
11.
Koniges, A., and Anderson, D.1987. ILUBCG2: A preconditioned bi-conjugate gradient routine for the solution of linear asymmetric matrix equations arising from 9-point discretizations. Comp. Phys. Commun.43:297-302.
12.
Lapidus, L., and Pinder, G.1981. Numerical solution of partial differential equations in engineering and science. New York: Wiley.
13.
Meijerink, J., and Van Der Vorst, H.1977. An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix . Math. Comp.31:148-162.
14.
Meurant, G.1984. The block preconditioned conjugate gradient method on vector computers. BIT24:623-633.
15.
Polak, S., Heijer, C., Schilders, W., and Markowich, P.1987. Semiconductor device modeling from the numerical point of view. Internat. J. Numer. Methods Engrg.24:763-838.
16.
Radicati di Brozolo, G., and Robert, Y.1988. Parallel and vector conjugate gradient-like algorithms for sparse nonsymmetric systems. Technical report. IBM ECSEC, Italy.
17.
Sonneveld, P.1989. CGS, a fast Lanczos-type solver for nonsymmetric systems . SIAM J. Sci. Statist. Comput.10:36-52.
18.
Van DerVorst, H.1982. A vectorizable variant of some ICCG methods. SIAM J. Sci. Statist. Comput.3:350-356.
19.
Van Der Vorst, H.1989a. High performance preconditioning. SIAM J. Sci. Statist. Comput.10(6):1174-1185.
20.
Van Der Vorst, H.1989b. The convergence behaviour of some iterative solution methods. Report 89-19. Delft University of Technology, The Netherlands.
21.
Vinsome, P.W.1976. Orthomin, an iterative method for solving sparse sets of simultaneous linear equations. SPE 5729. Society of Petroleum Engineers of AIME.
22.
Widlund, O.1978. A Lanczos method for a class of nonsymmetric systems of linear equations. SIAM J. Numer. Anal.15:801-812.
