Dynamic Load Balancing for PDE Solvers on 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. Computing Systems in Engineering, 2:135-148, 1991.



Fri Aug 13 13:42:59 BST 2004