TOWARD EFFICIENT UNSTRUCTURED MULTIGRID PREPROCESSING

The multigrid method is a general and powerful means of accelerating t he convergence of discrete iterative methods for solving partial diffe rential equations (PDEs) and similar problems. The adaptation of the m ultigrid method to unstructured meshes is important in solving problem s with complex geometries. Such problems lie on the forefront of many scientific and engineering fields. Unfortunately, multigrid schemes on unstructured meshes require significantly more preprocessing than on structured meshes. In fact, preprocessing can be a major part of the s olution task and, for many applications, must be executed repeatedly I n addition, the large computational requirements of realistic PDEs, ac curately discretized on unstructured meshes, make such computations ca ndidates for parallel or distributed processing. This adds problem par titioning as a preprocessing task. We propose and examine experimental ly an automatic and unified strategy to perform several unstructured m ultigrid preprocessing tasks. Our strategy is based on dominating sets in the unstructured meshes. We also suggest several alternative relat ed strategies. Our experiments evaluate the performance of two preproc essing tasks: coarse-mesh generation and domain partitioning. The expe riments suggest that our preprocessing strategy produces high-quality meshes that give good multigrid performance. Our strategy also produce s domain partitions that are reasonably load balanced with relatively small edge cuts. Overall, we conclude that simple, integrated algorith mic strategies and data structures can make tedious preprocessing task s more efficient and more automated-a necessary step toward the practi cal application of unstructured multigrid methods.