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 2 (February 14, 1992) Happy Valentine's Day

Today's topics:

     GMD Communications Library
     Multigrid Course


Date: Tue, 28 Jan 92 18:03:25 GMT
From: (Hubert Ritzdorf)
Subject: The GMD Communications Library

                        A survey of
     the GMD Communications Library for Grid-Oriented Problems

One important class of applications for high performance parallel
computers is based on regular grid data structures. Multigrid and
CFD codes using finite difference or finite volume discretizations
fall into this category. As the communication parts of these programs
are similar, a central communications library has been created, with
subroutines covering all communication requirements of the parallel
application programs (the communication of all the multigrid programs
developed in Institute I1 of the GMD is performed by the Communications
Library). Because this GMD Communications Library is based on the
ANL/GMD Macros (PARMACS), the library and the application programs
are portable between all machines for which the PARMACS are available.

The GMD Communications Library is, of course, not the first subroutine
library for inter-process communication on parallel machines. The
philosophy of this library, however, is that it is written on a fairly
high level rather than simply exchanging, for example, a send
operation by a more portable construct. Instead, more complex tasks
are performed by the library routines, facilitating the optimization
of the underlying algorithm on the machine used.

In the definition of the communications library routines, care has been
taken in order that they are not designed to the special requirements
of only one application. This would obviously unnecessarily restrict
the range of use. Furthermore, it is important that the library supplies
routines for as many communication tasks of the applications
program as possible, because otherwise the user again has to
write special communication routines himself.

The definition of the library is a dynamic process (currently, the
library contains about 40,000 lines of code); additions are made
as new requirements become apparent. So far, all communication
requirements of multigrid programs and similar, grid-related problems,
in two- and three-dimensions on rectangular or cubic domains are
covered.  Often, for CFD applications, block-structured domains are used.
Library routines for these more general domains have, to date, only
been implemented for 2-dimensional block-structures.

Currently, the Communications Library for 2- and 3-dimensional
process grids performs the following tasks (among other tasks):

 * Creation of node processes
 * Exchange of grid function values along inner boundaries
 * Redistribution of grid functions (``agglomeration''),
   change of the process grid (for coarse multigrid levels).

The Communications Library for 2-dimensional block-structured grids
performs the following tasks (among other tasks):

 * Creation of node processes
 * Transferring the grid coordinates to the node processes
 * Distribution of alteration rights at block boundaries
 * Setting up the update sequence to exchange the grid functions
   along inner boundaries
 * Computation of the areas which have to be sent to the
   neighbouring blocks
 * Exchange of the grid functions along inner boundaries

The following tasks can also be performed in a process grid application
as well as in a block-structured application:

 * Initialization and termination of the host process
 * Global operations (for example additions, supremum norms, ...)
   over all node processes
 * Send of subarrays to a specific process
 * Node triggered abort of the distributed application
 * Writing messages of grid functions from the node processes
 * Process synchronization
 * Inspection of the mailbox
 * A Link between the Communications Library and the ANL/GMD Macros

It is planned to integrate cell-centred discretization schemes and
local refinements in the block-structured part of the Communications

The GMD Communications Library is available from the GMD
(contact Hubert Ritzdorf, and from PALLAS GmbH.


Date: Tue, 28 Jan 92 17:47:27 GMT
From: (Hubert Ritzdorf)
Subject: Some Papers of Possible Interest

\item Brakhagen F.; Fogwell T.W.:
 {\it Multigrid Methods for Systems of Partial Differential Equations
 with Discontinuous Coefficients.}
 Proceedings of the Third International Conference on Hyperbolic
 Problems, Uppsala, Sweden, June 11--15, 1990
 (B. Engquist, B. Gustafson eds.), Studentlitteratur, Lund, Sweden, 1991.

\item Brakhagen F.; Fogwell T.W.:
 {\it Multigrid Methods for the Fully Implicit Formulation of the Equations
 for Multiphase Flow in Porous Media.}
 Proceedings of the Third European Conference on Multigrid Methods, Bonn,
 October 1--4, 1990, Multigrid Methods : Special Topics and Applications II,
 GMD-Studie Nr. 189, St. Augustin, 1991 (W. Hackbusch, U. Trottenberg eds.).

\item G\"artel, U.; Ressel, K.:
 {Parallel Multigrid : Grid Partitioning versus Domain Decomposition.}
 Arbeitspapiere der GMD, Nr. 599, GMD, St.  Augustin, 1991

\item Hempel, R.; Ritzdorf, H.:
 {\it The GMD Communications Library for Grid--Oriented Problems.}
 Arbeitspapiere der GMD, Nr. 589, GMD, St.  Augustin, 1991

\item Hempel, R.; Ritzdorf, H.:
 {\it The GMD Communications Library for Grid--Oriented Problems.
  -- User's Reference Manual --}
 Internal documentation, GMD, St.  Augustin, 1991

\item Joppich, W.:
 {\it A Multigrid Algorithm with Time-dependent, locally refined Grids
 for Solving the Nonlinear Diffusion Equation on a Nonrectangular
 Geometry - Practical Aspects.}
 Arbeitspapiere der GMD, Nr. 516, GMD, St. Augustin, 1991

\item Joppich, W.; Lorentz, R. A.:
 {\it High Order Positive, Monotone and Convex Multigrid Interpolations.}
 Arbeitspapiere der GMD, Nr. 558, GMD, St. Augustin, 1991

\item Lonsdale, G.; Sch\"uller, A.: {\it
 Parallel and vector aspects of a multigrid Navier-Stokes solver.}
 Arbeitspapiere der GMD, Nr. 550, GMD, St.  Augustin, 1991
 (submitted for publication in SIAM J. on Scientific and Statistical

\item Lonsdale, G.; Sch\"uller, A.: {\it
 Maintaining multigrid and parallel efficiency for the
 Navier-Stokes equations.} Proceedings of the Conference on
 ``Parallel Computational Fluid Dynamics'', Stuttgart, Germany,
 10-12 June 1991 (Reinsch et al., eds.), Elsevier Science
 Publishers B.V., Amsterdam.

\item Lonsdale, G.; St\"uben, K.: {\it The LiSS Package.}
 Arbeitspapiere der GMD, Nr. 524, GMD, St. Augustin, 1991

\item Lorentz, R. A.; Madych, W.R.:
 {\it Spline Wavelets for Ordinary Differential Equations.}
 Arbeitspapiere der GMD, Nr. 562, GMD, St. Augustin, 1991

\item Lorentz, R. A.; Madych, W.R.:
 {\it Wavelets and Generalized Box Splines.}
 Arbeitspapiere der GMD, Nr. 563, GMD, St.  Augustin, 1991

\item McBryan, O.A.; Frederickson, P.O.; Linden, J.; Sch\"uller, A.;
 Solchenbach, K.; St\"uben, K.; Thole, C.-A.; Trottenberg, U.:  {\it
 Multigrid methods on parallel computers -- a survey of recent
 developments.} IMPACT of Computing in Science and Engineering 3, 1-75,

\item Sch\"uller, A.; Solchenbach, K.; Trottenberg, U.: {\it
 Grid partitioning for CFD applications.} Proceedings of the
 Conference on ``Parallel Computational Fluid Dynamics'',
 Stuttgart, Germany, 10-12 June 1991 (Reinsch et al., eds.),
 Elsevier Science Publishers B.V., Amsterdam.

\item Sch\"uller, A.: {\it
 Parallelizing particle simulations based on the Boltzmann equation.}
 Arbeitspapiere der GMD, Nr. 557, GMD, St.  Augustin, 1991
 (to be published 1992 in Parallel Computing).


Date: Tue, 4 Feb 92 12:42:14 GMT
From: (Hubert Ritzdorf)
Subject: Multigrid Course

Multigrid Course 1992  -- GMD-Sankt Augustin

The GMD will give a multigrid course on June 22 - 26, 1992 at Sankt
Augustin near Bonn, Germany.  The principal lecturer is Professor Achi
Brandt from the Weizmann Institute, Rehovot, Israel, one of the pioneers
of multigrid.  The other lecturers are members of the GMD multigrid
research group.  The topics of this course will cover the basic
principles of multigrid, recent developments and applications.

The main scope of the course is to provide with an understanding of
multigrid. The visitor will, at the end of the course, be able to write
a multigrid program for model problems. Additionally, the course will
supply with an overview of multigrid application and recent research
activities. The course is especially designed for all those which have
to solve partial differential equations in practice.

Multigrid, or more general multilevel computational methods have evolved
into an independent discipline by itself, interacting with numerous
engineering application areas and impacting fundamental developments in
several sciences. The recent past shows an increased development of
multilevel solvers for various areas, including: aerodynamics,
atmospheric and oceanic research, structural mechanics, robotics,
quantum mechanics, astrophysics, condensed matter, VLSI design, and
tomography.  This enormous spectrum was opened by the following facts:
The typical multilevel algorithm uses local processing on each scale of
the problem, with inter-scale interactions.  As a result, fine scales
can be employed very sparingly, and sometimes only at special or
representative small regions.

The theory states that a multigrid solution is generally obtained in a
time directly proportional to the number of unknowns on serial
computers. As indicated by the above examples, further research and
developments showed the potential of the multigrid principle which
allows the application of multigrid algorithms and multigrid ideas to
highly complex problems.  The inherent locality of the multigrid
components allows a very efficient parallelization with nearly optimal
speed up.  Recent research activities have verified this for a wide
class of parallel machines.

For further information, please contact:
       Barbara Steckel, Wolfgang Joppich
       Institut f\"ur Methodische Grundlagen (I1/T)
       Gesellschaft f\"ur Mathematik und Datenverarbeitung (GMD)
       Postfach 1316
       W-5205 Sankt Augustin 1
       Federal Republic of Germany
       Phone: (0)2241 14 2768 or - 2748
       Fax: (0)2241 14 2460
       Email: gmap16@dbngmd21.bitnet


End of MGNet Digest