Send mail to:             for the digests or bakeoff
            for comments or help
 Current editor:  Craig Douglas       
Anonymous ftp repository: (

Today's editor:  Craig Douglas (

Volume 2, Number 8 (August 29, 1992)

Today's topics:

     Unstructured grids replies (3)
     Paper related to multigrid for unstructured grids
     Cyclic reduction and multigrid
     Paper on the robustness and efficiency of the fully adaptive multigrid


Date: Wed, 29 Jul 92 19:25:34 MET DST
From: (Johan De Keyser)
Subject: Multigrid for unstructured meshes (in reply to your mgnet message)


In reply to your question about multigrid for unstructured meshes,
I dug up the following references :

- Unstructured Multigridding by Volume Agglomeration,
  Lallemand, M.-H. and Steve, H. and Dervieux A.,
  INRIA, Rapports de Recherche 1224, Sophia Antipolis, 1990

- The design and implementation of a parallel unstructured Euler
  solver using software primitives,
  Das, R. and Mavriplis, D. and Saltz, J. and Gupta, S. and Ponnusamy, R.,
  Proceedings of the 30th Aerospace Sciences Meeting and Exhibit,
  Paper AIAA-92-0562, 1992

- Accurate multigrid solution of the Euler equations on unstructured
  and adaptive meshes, Mavriplis D.,
  ICASE report 88-40, 1988

and some of my own work

- Incremental Mapping for Solution-Adaptive Multigrid Hierarchies,
  De Keyser, J. and Roose, D.,
  Proceedings of the Scalable High Performance Computing Conference 92,
  IEEE Computer Society Press, pp. 401-408,

Personally, I am interested in the numerical aspects of such
multigrid techniques, and in their implementation on distributed
memory parallel computers (a.o. the load balancing problem).
I have some tech reports regarding this work; I can send them to
you if you're interested.


Date: Wed, 29 Jul 92 23:17:34 CDT
From: groucho!scott@math.UH.EDU ("L. Ridgway Scott")
Subject: unstructured grids

One paper that may be of interest to you is by me and Shangyou Zhang,
Higher Dimensional Non-nested Multigrid Methods, Math. Comp. 58 
(1992), 457--466. Grids in different levels are allowed to be only
weakly related, yet convergence still holds.

Shangyou has written a code implementing non-nested multigrid in
3-D; the key point is to be able to construct inter-grid transfers
efficiently, so only a limited class of non-nested refinements have
been implemented so far. 

For more information:
        Ridgway Scott -
        Shangyou Zhang -


Date: Fri, 21 Aug 1992 18:10:31 +0200
From: Ulrich Ruede 
Subject: Re: unstructured multigrid

In the mgnet Digest of July 29, 1992 (V2N7)
Horst Simon ( has asked about ideas and references
for multigrid methods on unstructured grids.

Most multigrid methods for unstructured grids at least assume a nested
(or almost nested) hierarchy of meshes. The only fully unstructured
mesh approach I can remember goes back to Loehner and Morgan:

author =        {R. L\"{o}hner and K. Morgan},
title =         "Unstructured Multigrid Methods",
booktitle =     {Multigrid Methods: Special Topics and Applications,
                 Papers presented at the 2nd European Conference on Multigrid
                 Methods, Cologne, October 1-4, 1985},
year =          "1986",
note =          "GMD Studien Vol. 110",

For nested, unstructured meshes there is the work by Randy Bank (the
PLTMG package), Rivara, Mitchell, and myself (papers are available by
ftp from mgnet). The work done for hierarchical basis and BPX
preconditioners is closely related, though multigrid purists may not
accept it as *real* multigrid.  There are many theoretical papers, but
working codes are less plentiful. Besides PLTMG, I know about the
program by Peter Leinen (
and the program by the group at the Konrad Zuse Zentrum in Berlin
( My own code exists as a prototype and
is currently being redesigned. In this field there is much work in
progress, and I hope that the other people working in unstructured
multigrid methods will respond directly.

If unstructured grids must be coarsened, algebraic multigrid may be a
good alternative.

Ulrich Ruede


Date: Wed, 29 Jul 92 19:58:56 MET DST
From: (Johan De Keyser)
Subject: Paper related to multigrid for unstructured grids


I am putting a report "" on the mgnet/incoming directory.
Sorry it is in postscript (quite large) because I included some ps pictures.
This report discusses parallelization of an unstructured multigrid solver
(for a simple linear hyperbolic equation), especially the load balancing
issues involved in this particular case.
The load balancing problem is solved by applying suitable partitioning
and mapping techniques.

I am currently experimenting with a parallel unstructured grid FAS-cycle
for the Euler equations, but I have not yet found the time to
write things down ...  As soon as I do, I'll let you know.

    Editor's Note:  This paper can be found in mgnet/papers/DeKeyser/

Partitioning and Mapping Adaptive Multigrid Hierarchies on 
Distributed Memory Computers

Johan De Keyser and Dirk Roose

Feb 1992

Report TW166
Department of Computer Science
Katholieke Universiteit Leuven 
Celestijnenlaan 200A
3001 Heverlee

Keywords : multigrid, finite volumes, data parallelism, load balancing,
           distributed memory computers

Abstract :

The full multigrid method uses a hierarchy of successively finer grids.
In a solution-adaptive grid hierarchy each grid is obtained 
by adaptive refinement of the grid on the previous level.
On a distributed memory multiprocessor, each grid level must be
partitioned and mapped so as to minimize the multigrid cycle execution time.
In this report several grid partitioning and load (re)mapping strategies
that deal with this problem are compared.
The performance of such parallel adaptive multigrid algorithms has been
evaluated on an iPSC hypercube for an irregular finite volume discretization
of a linear first-order hyperbolic partial differential equation
on a two-dimensional domain.


Date: Wed, 12 Aug 92 09:01:45 PDT
From: (Michael Holst)
Subject: Cyclic reduction and multigrid

Do you know if anyone has worked out the connection between 
cyclic reduction and multigrid (in dimensions > 1) ??

Thanks for any help you can provide,

    Editor's Note:  I think many readers would like to know this, too.
    -------------   Please cc this list.


Date: Fri, 21 Aug 1992 17:19:12 +0200
From: Ulrich Ruede 
Subject: new paper downloaded to mgnet

I've downloaded a short paper
        "On the robustness and efficiency of the fully adaptive
         multigrid method"
to the mgnet ftp repository. The paper has been submitted for the
        Proceedings of the Sixth International Conference
        on Domain Decomposition in Science and Engineering
On the mgnet the submission consists of a file
containing the abstract as a plain ascii file, and the file
that contains the full paper as a compressed dvi-file.

On the Robustness and Efficiency of the Fully Adaptive Multigrid Method
        Ulrich Ruede

        Institut fuer Informatik
        Technische Universitaet Muenchen
        Arcisstr. 21,
        D-8000 Muenchen 2,  Germany

AMS Classifications:    65N55, 65N15, 65N50}
Keywords:       fully adaptive multigrid, mesh refinement,
virtual global grids, error estimates, multilevel additive Schwarz method


The fully adaptive multigrid method (FAMe) is a finite element based
elliptic solver integrating self-adaptivity, error estimation and
efficient iterative solution.  Refined elements are not restricted to
predetermined regions and need not be grouped in patches.  Instead,
whether an element is refined, is decided individually for each element
using an integrated error indicator.  The refinement process induces a
multilevel structure and therefore a natural decomposition of the
solution space into a nested sequence.  This can be exploited to define
an efficient solver and error estimator.

    Editor's Note:  This paper can be found in mgnet/papers/Ruede/robust.dvi.Z


End of MGNet Digest