In this paper we review several methods for solving large sparse linear systems arising from discretization of elliptic partial differential equations on parallel com puters. The main idea is to use domain decomposition to introduce some parallelism. We describe techniques such as the Schwarz algorithm and the block incomplete factorization method, showing with examples the effi ciency of these domain decomposition techniques when the number of subdomains is increased.
Get full access to this article
View all access options for this article.
References
1.
Björstad, P., and Widlund, O.B.1986. Iterative methods for the solution of elliptic problems on regions partitioned into substructures. SIAM J. Numer. Anal.23(6):1097-1120.
2.
Bramble, J.H., Pasciak, J.E., and Schatz, A.H.1986. The construction of preconditioners for elliptic problems by substructuring: I, Math. Comp.47(175):103-104.
3.
Chan, T.1988. Proceedings of the second international symposium on domain decomposition methods for partial dafferential equcztions. Philadelphia: SIAM.
4.
Chan, T., and Resasco, D.1985. A domain decomposition fast Poisson solver on a rectangle . Yale Univ. Report YALEU/DCS/RR 409. New Haven: Yale University.
5.
Concus, P., Golub, G.H., and Meurant, G.1985. Block preconditioning for the conjugate gradient method . SIAM J. Sci. Statist. Comput.6:220-252.
6.
Concus, P., Golub, G.H., and O'Leary, D.P.1976. A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations. In Sparse matrix computations , edited by J. R. Bunch and D. Rose.New York: Academic Press.
7.
Dryja, M., Proskurowski, W., and Widlund, O.B.1987. Numerical experiments and implementation of domain decomposition methods with cross points for the model problem. In Advances in computer methods for PDEs: VI. New Brunswick, N.J.: IMACS, pp. 23-27.
8.
Glowinski, R., Golub, G.H., Meurant, G., and Periaux, J.1988. Proceedings of the first international symposium on domain decomposition methods for partial differential equations. Philadelphia: SIAM.
9.
Golub, G.H., and Mayers, D.1984. The use of preconditioning over irregular regions . In Computing methods in applied science and engineering VI , edited by R. Glowinski and J. L. Lions.New York: North-Holland .
10.
Hestenes, M.R., and Stiefel, E.1952. Methods of conjugate gradients for solving linear systems . J. Res. Nat. Bur. Standards49:409-436.
11.
Lions, P.L.1988. On the Schwarz alternating method I. In Proceedings of the first international symposium on damain decomposition methods for partial differential equations, edited by R. Glowinski, G. H. Golub, G. Meurant, and J. Periaux.Philadelphia: SIAM, pp. 1-42.
12.
Meurant, G.1987. Multitasking the conjugate gradient method on the CRAY X-MP/48. Parallel Comput.5:267-280.
13.
Meurant, G.1988a. Domain decomposition vs block preconditioning . In Proceedings of the first international symposium on domain decomposition methods for partial differential equations, edited by R. Glowinski, G. H. Golub, G. Meurant, and J. Periaux. Philadelphia: SIAM, pp. 231-249.
14.
Meurant, G.1988b. Conjugate gradient preconditioners for parallel computers . In Proceedings of the third SIAM conference on parallel processing for scientific computing. Philadelphia : SIAM.
15.
Meurant, G.1988c. Domain decomposition preconditioners for nonsymmetric problems. In Proceedings of the second international symposium on domain decomposition methods for partial differential equations , edited by T. Chan. Philadelphia: SIAM.
16.
Meurant, G.1988d. Domain decomposition preconditioners for the conjugate gradient method. Calcolo, in press.
17.
Oliger, J., Skamarock, W., and Tang, W.P.1986. Convergence analysis and acceleration of the Schwarz alternating method. Stanford University CLaSSiC-86-12.
18.
Rodrigue, G., and Simon, J.1984. A generalization of the numerical Schwarz algorithm . In Camputing methods in applied sciences and engineering VI, edited by R. Glowinski and J. L. Lions.New York: North-Holland , pp. 273-283.
19.
Rodrigue, G., and Saylor, P.1985. Inner/outer iterative methods and numerical Schwarz algorithms . Lawrence Livermore National Laboratory UCRL-92077-II.
20.
Swarztrauber, P.N., and Sweet, R.A.1975. Efficient Fortran subprograms for the solution of elliptic partial differential equations. Tech. Note TN/1A-109. Boulder, Col.: Nat. Ctr. for Atmospheric Res.
21.
Schwarz, H.A.1869. Über einige abbildungsaufgaben. Ges. Math. Abh.11:65-83.
22.
Young, D.M.1971. Iterative solution of large linear systems. New York: Academic Press.
