An interesting algorithm is described for the parallel solution of the two-dimensional model problem (∂ u&slash; ∂ t ) - a δ u = f in &OHgr; × ( 0 , T ], u | ∂ &OHgr; = 0, u | t = 0 = u 0, where &OHgr; is a convex polygon and f may be time-dependent. The domain &OHgr; is triangulated and &OHgr; = ∪ nj = 1 &OHgr;&dgr;i, where the &OHgr;&dgr;i are overlapping subdomains with overlaps ∼ &dgr;. Each &OHgr;&dgr;i is a union of elements of the triangulation. At each time step, on each subdomain, one computes the Crank Nicolson Galerkin approximation based on piecewise linear elements. Boundary conditions on the subdomain boundaries are determined using linear extrapolation in the theoretical considerations but quadratic extrapolation in the numerical experiments. From the local solutions, which can be determined completely in parallel, a global single-valued function is constructed in a straightforward way. The authors prove that the algorithm is second-order accurate in space and time provided that the overlap, &dgr;, is sufficiently large. Numerical testing indicates that an overlap of 3 h or 4 h is adequate, where h is the diameter of the triangulation. The primary advantage of the algorithm is that it requires no global communication. Numerical tests on a transputer system confirm the theoretical results.
As the authors indicate, this type of method is attractive when the computational domain splits into several components, or when an effectively parallelized global algorithm is not available. In the latter case, it may even be used as a preconditioner within a global iteration process.
