MULTILEVEL DIFFUSION SCHEMES FOR REPARTITIONING OF ADAPTIVE MESHES

For a large class of irregular mesh applications, the structure of the mesh changes from one phase of the computation to the next, Eventuall y, as the mesh evolves, the adapted mesh has to be repartitioned to en sure good load balance, If this new graph is partitioned from scratch, it may lead to an excessive migration of data among processors, In th is paper, we present schemes for computing repartitionings of adaptive ly refined meshes that perform diffusion of vertices in a multilevel f ramework, These schemes try to minimize vertex movement without signif icantly compromising the edge-cut, We present heuristics to control th e tradeoff between edge-cut and vertex migration costs, We also show t hat multilevel diffusion produces results with improved edge-cuts over single-level diffusion, and is better able to make use of heuristics to control the tradeoff between edge-cut and vertex migration costs th an single-level diffusion. (C) 1997 Academic Press.