A Characterization of Mapping Unstructured Grids onto Structured
Grids and Using Multigrid as a Preconditioner

Sachit Malhotra
Yale Center for Parallel Supercomputing
Department of Computer Science
Yale University
New Haven, CT 06520-8285 USA

Craig C. Douglas
IBM T. J. Watson Research Center
Yorktown Heights, NY, USA and
Computer Science Department
Yale University
New Haven, CT, USA

Martin H. Schultz
Department of Computer Science
Yale University
New Haven, CT 06520-8285 USA


Many problems based on unstructured grids provide a natural multigrid framework due to using an adaptive gridding procedure. When the grids are saved, even starting from just a fine grid problem poses no serious theoretical difficulties in applying multigrid.

A more difficult case occurs when a highly unstructured grid problem is to be solved with no hints how the grid was produced. Here, there may be no natural multigrid structure and applying such a solver may be quite difficult to do.

Since unstructured grids play a vital role in scientific computing, many modifications have been proposed in order to apply a fast, robust multigrid solver. One suggested solution is to map the unstructured grid onto a structured grid and then apply multigrid to a sequence of structured grids as a preconditioner.

In this paper, we derive both general upper and lower bounds on the condition number of this procedure in terms of computable grid parameters.

We provide examples to illuminate when this preconditioner is a useful (e.g., p or h-p formulated finite element problems on semi-structured grids) or should be avoided (e.g., typical computational fluid dynamics (CFD) or boundary layer problems). We show that unless great care is taken, this mapping can lead to a system with a high condition number which eliminates the advantage of the multigrid method.

Contributed May 31, 1996.