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

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

                                C. C. Douglas
             IBM Research Division, T. J. Watson Research Center
                     Yorktown Heights, NY 10598-0218 and
                        Department of Computer Science
                               Yale University
                         New Haven, CT 06520-8285 USA

                                M. H. Schultz
                   Yale Center for Parallel Supercomputing
                        Department of Computer Science
                               Yale University
                         New Haven, CT 06520-8285 USA


ABSTRACT

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.