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
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.

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 |