The Scalability of Mesh Improvement Algorithms

In this paper we develop a common framework to explore the scalability of three improvement strategies for unstructured meshes: adaptive refinement, vertex smoothing, and edge flipping. We give a general parallel algorithm for these strategies based on defining, for each algorithm, an elemental operation and a task graph. By choosing the correct task graph, we can ensure the correct parallel execution of the algorithms independent of implementation. Finally, we present experimental results obtained on an IBM SP system and use these results to investigate, in practice, the scaling and relative costs of these algorithms.