Wavefront Diffusion and LMSR: Algorithms for Dynamic Repartitioning of Adaptive Meshes

Date of Submission: 
October 10, 1998
Report Number: 
98-034
Abstract: 
Existing state-of-the-art schemes for dynamic repartitioning of adaptive meshes can be classified as either diffusion-based schemes or scratch-remap schemes. We present a new scratch-remap scheme called Locally-Matched Multilevel Scratch-Remap (or simply LMSR). The LMSR scheme tries to compute a partitioning that has a high overlap with the existing partitioning. We show that LMSR decreases the amount of vertex migration required to balance the graph compared to current scratch-remap schemes, particularly for slightly imbalanced graphs. We describe a new diffusion-based scheme that we refer to as Wavefront Diffusion. In Wavefront Diffusion, the flow of vertices moves in a wavefront from overweight to underweight domains. We show that Wavefront Diffusion obtains significantly lower vertex migration requirements while maintaining similar or better edge-cut results compared to existing diffusion algorithms, especially for highly imbalanced graphs. Further more, we compare Wavefront Diffusion with LMSR and show that the former scheme results in generally lower vertex migration requirements at the cost of lower quality edge-cuts. Our experimental results on parallel computers show that both schemes are highly scalable. For example, both are capable of repartitioning an eight million node graph in under three seconds on a 128-processor Cray T3E.