Toward efficient unstructured multigrid preprocessing

Susan E. Dorward, Lesley R. Matheson, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)12-33
Number of pages22
JournalInternational Journal of High Performance Computing Applications
Issue number1
StatePublished - 1997

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'Toward efficient unstructured multigrid preprocessing'. Together they form a unique fingerprint.

Cite this