An overlapping domain decomposition method for the parallelization of the solution of parabolic differential equations. (Eine überlappende Gebietszerlegungsmethode zur Parallelisierung der Lösung von parabolischen Differentialgleichungen.) (German) Zbl 0801.65094

Jäger, Jürgen

Heidelberg: Univ. Heidelberg, Naturwiss.-Math. Gesamtfak. 152 S. (1994).

The main subjects of this paper are a theoretical and practical investigation of an overlapping domain decomposition (ODD) method, which allows parallelization of the solution of parabolic partial differential equations, and a comparison of basic concepts of parallelization for parabolic problems concerning accuracy and parallel performance with respect to different parallel computer architectures.
First we describe an ODD-method introduced by Kuznetsov, prove stability and error estimates, present an extending extrapolation approach reducing the amount of overlapping by 35-70% and compare this method with an ODD- method proposed by Rannacher. For the consideration of parallel performance for parallelized iterative algorithms in the solution of time-dependent problems we introduce a model describing the different costs, idle time and efficiency depending on architecture parameters. Because the behaviour in practice of the considered ODD-method was unknown before, in the practical investigation we restrict ourselves to the heat conduction equation. As solver we use the cg-algorithm. We choose a two-dimensional model problem on an \(L\)-shaped domain using a refined tensor product grid and a decomposition into five subdomains.
We compare 3 parallelization strategies applying them in the solution for the model problem: 1) parallelization of the algorithm: data decomposition, 2) parallelization of the problem: ODD, 3) data decomposition preconditioned by ODD. Using the model presented above we simulate the solution process for the strong coupled architecture of a transputer system and the low coupled architecture of a workstation cluster. Furthermore we implement the different parallelization strategies on an IBM workstation cluster and make various time measurements.
We establish that the properties developed for the ODD-method theoretically above are confirmed in practice, we observe that the model gives nearly the same performance as the practical computations. The ODD- methods are appropriate for both types of architectures, while the data decmposition seems to be not suitable for low coupled systems.

Reviewer: J.Jäger (Heidelberg)

MSC:

65M55	Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs
65M15	Error bounds for initial value and initial-boundary value problems involving PDEs
65M12	Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs
35K15	Initial value problems for second-order parabolic equations
65Y05	Parallel numerical computation
65Y20	Complexity and performance of numerical algorithms

Keywords:

overlapping domain decomposition method; cg-algorithm; \(L\)-shaped domain; parallelization; parabolic problems; parallel performance; parallel computer architectures; stability; error estimates; extrapolation; heat conduction equation; data decomposition