A new paradigm for parallel adaptive meshing algorithms

We present a new approach to the use of parallel computers with adaptive fi nite element methods. This approach addresses the load balancing problem in a new way, requiring far less communication than current approaches. It al so allows existing sequential adaptive PDE codes such as PLTMG and MC to ru n in a parallel environment without a large investment in recoding. In this new approach, the load balancing problem is reduced to the numerical solut ion of a small elliptic problem on a single processor, using a sequential a daptive solver, without requiring any modi cations to the sequential solver . The small elliptic problem is used to produce a posteriori error estimate s to predict future element densities in the mesh, which are then used in a weighted recursive spectral bisection of the initial mesh. The bulk of the calculation then takes place independently on each processor, with no comm unication, using possibly the same sequential adaptive solver. Each process or adapts its region of the mesh independently, and a nearly load-balanced mesh distribution is usually obtained as a result of the initial weighted s pectral bisection. Only the initial fan-out of the mesh decomposition to th e processors requires communication. Two additional steps requiring boundar y exchange communication may be employed after the individual processors re ach an adapted solution, namely, the construction of a global conforming me sh from the independent subproblems, followed by a final smoothing phase us ing the subdomain solutions as an initial guess. We present a series of con vincing numerical experiments which illustrate the effectiveness of this ap proach. The justification of the initial refinement prediction step, as wel l as the justification of skipping the two communication-intensive steps, i s supported by some recent [J. Xu and A. Zhou, Math. Comp., to appear] and not so recent [J. A. Nitsche and A. H. Schatz, Math. Comp., 28 (1974), pp. 937-958; A. H. Schatz and L. B. Wahlbin, Math. Comp., 31 (1977), pp. 414-44 2; A. H. Schatz and L. B. Wahlbin, Math. Comp., 64 (1995), pp. 907-928] res ults on local a priori and a posteriori error estimation.