Dynamic Load-Balancing For PDE Solvers
Using Adaptive Unstructured Meshes

Chris Walshaw and Martin Berzins

Abstract:

Modern PDE solvers written for time-dependent problems increasingly employ adaptive unstructured meshes (see Flaherty et al. [1]) in order to both increase efficiency and control the numerical error. If a distributed memory parallel computer is to be used, there arises the significant problem of dividing up the domain equally amongst the processors whilst minimising the inter-subdomain dependencies. A number of graph based algorithms have recently been proposed for steady state calculations, for example [2] & [3]. This paper considers an extension to such methods which renders them more suitable for time-dependent problems in which the mesh may be changed frequently.

References

1

J. E. Flaherty, P. J. Paslow, M. S. Shepherd, and J. D. Vasilakis. Adaptive Methods for Partial Differential Equations. In Proc. of Workshop on Adaptive Computational Methods for Partial Differential Equations, Rensseleer Poly. Inst., 1988, SIAM, Philadelphia, 1989.

2

B. Hendrickson and R. Leland. An Improved Spectral Graph Partitioning Algorithm for Mapping Parallel Computations. Tech. Rep. SAND 92-1460, Sandia National Labs, Albuquerque, NM., 1992.

3

H. D. Simon. Partitioning of Unstructured Problems for Parallel Processing. Tech. Rep. RNR-91-08, NASA Ames Research Center (to appear in Computing Systems in Engineering), 1991.