Send mail to: mgnet@cs.yale.edu for the digests or bakeoff
mgnet-requests@cs.yale.edu for comments or help
Current editor: Craig Douglas douglas-craig@cs.yale.edu
Anonymous ftp repository: casper.cs.yale.edu (128.36.12.1)
Today's editor: Craig Douglas (douglas-craig@cs.yale.edu)
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
method
-------------------------------------------------------
Date: Wed, 29 Jul 92 19:25:34 MET DST
From: Johan.DeKeyser@cs.kuleuven.ac.be (Johan De Keyser)
Subject: Multigrid for unstructured meshes (in reply to your mgnet message)
Hi,
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,
1992
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 - scott@uh.edu
Shangyou Zhang - szhang@math.udel.edu
-------------------------------------------------------
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 (simon@nas.nasa.gov) 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:
@inproceedings{Loehner86a,
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 (peter@tue-num2.mathematik.uni-tuebingen.de)
and the program by the group at the Konrad Zuse Zentrum in Berlin
(deuflhard@sc.zib-berlin.dbp.de). 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.DeKeyser@cs.kuleuven.ac.be (Johan De Keyser)
Subject: Paper related to multigrid for unstructured grids
Hi,
I am putting a report "imap.ps" 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/imaps.ps
-------------
Partitioning and Mapping Adaptive Multigrid Hierarchies on
Distributed Memory Computers
Johan De Keyser and Dirk Roose
johandk@cs.kuleuven.ac.be
Feb 1992
Report TW166
Department of Computer Science
Katholieke Universiteit Leuven
Celestijnenlaan 200A
3001 Heverlee
Belgium
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: holst@mercury.llnl.gov (Michael Holst)
Subject: Cyclic reduction and multigrid
Cc: holst@cs.uiuc.edu
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,
-mike
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
robust.abstract
containing the abstract as a plain ascii file, and the file
robust.dvi.Z
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
ruede@informatik.tu-muenchen.de
AMS Classifications: 65N55, 65N15, 65N50}
Keywords: fully adaptive multigrid, mesh refinement,
virtual global grids, error estimates, multilevel additive Schwarz method
ABSTRACT
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
**************************