Dynamic Load Balancing for PDE Solvers on Adaptive Unstructured Meshes

Chris Walshaw and Martin Berzins


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.


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.

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.

H. D. Simon. Partitioning of Unstructured Problems for Parallel Processing. Computing Systems in Engineering, 2:135-148, 1991.

Fri Aug 13 13:42:59 BST 2004