Toward efficient unstructured multigrid preprocessing

The multigrid method is a general and powerful means of accelerating the convergence of discrete iterative methods for solving partial differential equations (PDEs) and similar problems. The adaptation of the multigrid method to unstructured meshes is important in solving problems 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 solution task and, for many applications, must be executed repeatedly. In addition, the large computational requirements of realistic PDEs, accurately discretized on unstructured meshes, make such computations candidates for parallel or distributed processing. This adds problem partitioning as a preprocessing task. We propose and examine experimentally an automatic and unified strategy to perform several unstructured multigrid preprocessing tasks. Our strategy is based on dominating sets in the unstructured meshes. We also suggest several alternative related strategies. Our experiments evaluate the performance of two preprocessing tasks: coarse-mesh generation and domain partitioning. The experiments suggest that our preprocessing strategy produces high-quality meshes that give good multigrid performance. Our strategy also produces domain partitions that are reasonably load balanced with relatively small edge cuts. Overall, we conclude that simple, integrated algorithmic strategies and data structures can make tedious preprocessing tasks more efficient and more automated - a necessary step toward the practical application of unstructured multigrid methods.