Toward efficient unstructured multigrid preprocessing (extended abstract)

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 the solution of problems with complex geometries. 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 done repeatedly. In addition, the large computational requirements of realistic PDEs, accurately discretized on unstructured meshes, make such computations candidates for parallel or distributed processing, adding problem partitioning as a preprocessing task. We report on a project to apply ideas from graph theory and geometry to the solution of the preprocessing tasks required for the parallel implementation of unstructured multigrid methods. Our objective is to provide conceptually simple, efficient, and unified methods. In a previous conference paper, we proposed two bottom-up, graphbased methods and one top-down method. In this paper, we report on several sets of experiments designed to explore the practical aspects of one of the methods, based on independent dominating sets. The experiments studied the empirical properties of the mesh hierarchies generated by the method and the numerical performance of the multigrid method solving Laplace's equation using these mesh hierachies. The experiments also studied the domain partitions generated by the method. Our conclusion based on these preliminary experiments is that our simple, automatic methods provide excellent multigrid performance at low preprocessing cost.

Original languageEnglish (US)
Title of host publicationParallel Algorithms for Irregularly Structured Problems - 3rd International Workshop IRREGULAR 1996, Proceedings
EditorsAfonso Ferreira, Jose Rolim, Yousef Saad, Tao Yang
PublisherSpringer Verlag
Number of pages14
ISBN (Print)3540615490, 9783540615491
StatePublished - 1996
Event3rd International Workshop on Parallel Algorithms for Irregularly Structured Problems, IRREGULAR 1996 - Santa Barbara, United States
Duration: Aug 19 1996Aug 21 1996

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other3rd International Workshop on Parallel Algorithms for Irregularly Structured Problems, IRREGULAR 1996
Country/TerritoryUnited States
CitySanta Barbara

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this