TY - JOUR

T1 - Domain decomposition on parallel computers

AU - Gropp, William D.

AU - Keyes, David E.

N1 - Funding Information:
* Research Report YALEU/DCS/RR-723. W.D.G. was supported in part by the Office of Naval Research under Contract N00014-86-K-03 10 and the National Science Foundation under Contract DCR 852 145 1. D.E.K. was supported in part by the National Science Foundation under Contract EET-8707 109.

PY - 1989/12

Y1 - 1989/12

N2 - We consider the application of domain decomposition techniques to the solution of sparse linear systems arising from implicit PDE discretizations on parallel computers. Representatives of two popular MIMD architectures, message passing (the Intel iPSC/2-SX) and shared memory (the Encore Multimax 320), are employed. We run the same numerical experiments on each, namely stripwise and boxwise decompositions of the unit square, using up to 64 subdomains and containing up to 64K degrees of freedom. We produce a tight-fitting complexity model for the former and discuss the difficulty of doing so for the latter. We also evaluate which of three types of domain decomposition preconditioners that have appeared in the literature of self-adjoint elliptic problems are most efficient in different regions of machine-problem parameter space. Some form of global sharing of information in the preconditioner is required for efficient overall parallel implementation in the region of most practical interest (large problem sizes and large numbers of processors); otherwise, an increasing iteration count inveighs against the gains of concurrency. Our results on a per iteration basis also hold for sparse discrete systems arising from other types of partial differential equations, but in the absence of a theory for the dependence of the convergence rate upon the granularity of the decomposition, the overall results are only suggestive for more general systems.

AB - We consider the application of domain decomposition techniques to the solution of sparse linear systems arising from implicit PDE discretizations on parallel computers. Representatives of two popular MIMD architectures, message passing (the Intel iPSC/2-SX) and shared memory (the Encore Multimax 320), are employed. We run the same numerical experiments on each, namely stripwise and boxwise decompositions of the unit square, using up to 64 subdomains and containing up to 64K degrees of freedom. We produce a tight-fitting complexity model for the former and discuss the difficulty of doing so for the latter. We also evaluate which of three types of domain decomposition preconditioners that have appeared in the literature of self-adjoint elliptic problems are most efficient in different regions of machine-problem parameter space. Some form of global sharing of information in the preconditioner is required for efficient overall parallel implementation in the region of most practical interest (large problem sizes and large numbers of processors); otherwise, an increasing iteration count inveighs against the gains of concurrency. Our results on a per iteration basis also hold for sparse discrete systems arising from other types of partial differential equations, but in the absence of a theory for the dependence of the convergence rate upon the granularity of the decomposition, the overall results are only suggestive for more general systems.

UR - http://www.scopus.com/inward/record.url?scp=0012787015&partnerID=8YFLogxK

U2 - 10.1016/0899-8248(89)90003-7

DO - 10.1016/0899-8248(89)90003-7

M3 - Article

AN - SCOPUS:0012787015

SN - 0899-8248

VL - 1

SP - 421

EP - 439

JO - IMPACT of Computing in Science and Engineering

JF - IMPACT of Computing in Science and Engineering

IS - 4

ER -