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 3, Number 7 (July 31, 1993)

Today's topics:

     EMG93 directory/conference
     Book Announcement
     Vandewalle references
     Oosterlee references
     More References
     Paper on Parabolic Multigrid and Waveform Relaxation 


Date: Fri, 30 Jul 1993 08:04:34 -0400
From: (Craig Douglas)
Subject: EMG93 directory/conference

The 4th EMG conference was held in Amsterdam.  Many people who attended went
on vacation immediately afterwards so a sumary has not yet been forwarded
here (hint:  see you name in lights for a summary before I have to write one).
Many thanks to the organizers for a very good conference.  Both Piet Hemker's
and Piet Wesseling's families deserve many thanks from all of us who attended.

I have received a couple of papers that were submitted to Piet Hemker for
inclusion in the proceedings of Fourth European Multigrid Conference.  I have
put them in a new directory, mgnet/EMG93.  See the README.mgnet file in that
directory for more information.  If I do not hear of any more papers, I will
print the abstracts next issue.  Hopefully, Piet Hemker will look upon this
as free disk space...


Date: Thu, 22 Jul 1993 15:31:38 +0200 (MET DST)
From: (Stefan Vandewalle)
Subject: Book Announcement

I would like to announce the publication of the book:

"Parallel Multigrid Waveform Relaxation for Parabolic Problems"
by Stefan Vandewalle, in the series Teubner-Skripten zur Numerik, 
B.G. Teubner Stuttgart, Germany, 1993.
(16.2x23.5 cm, 247 pages, DM 39.80, ISBN 3-519-02717-8)


Waveform relaxation is a highly parallel iterative method for solving very
large systems of ordinary differential equations.  Over the years this method
has been applied almost exclusively for the systems that model VLSI electronic

In the present work the author studies waveform relaxation methods for
parabolic partial differential equations of initial boundary-value and
time-periodic type.  It is shown both theoretically and by numerical
experimentation that waveform relaxation, when accelerated by using multigrid,
is a highly effective algorithm.  It combines a low serial complexity with a
high parallel efficiency and it is easily vectorisable.

The book starts with an introductory overview of the waveform relaxation
theory and practice, and provides an in-depth analysis of multigrid waveform
relaxation.  It discusses the parallel implementation of classical
time-stepping schemes and analyses the computational complexity of waveform
relaxation methods.  A large number of case- studies illustrate the
performance of the methods for linear and nonlinear problems.


Date: Thu, 22 Jul 1993 15:31:38 +0200 (MET DST)
From: (Stefan Vandewalle)
Subject: Vandewalle references

  author = "Vandewalle, S. and Piessens, R.",
  title  = "Efficient parallel algorithms for solving initial-boundary value
            and time-periodic parabolic partial differential equations",
  journal= "SIAM J. Sci. Stat. Comput.",
  volume = "13",
  year   = "1992",
  pages  = "1330--1346"
  author = "Vandewalle, S. and Piessens, R.",
  title  = "Numerical experiments with nonlinear multigrid waveform
            relaxation on a parallel processor",
  journal= "Applied Numerical Mathematics",
  volume = "8",
  year   = "1991",
  pages  = "149--161"
  author = "Vandewalle, S. and Piessens, R.",
  title  = "On dynamic iteration methods for solving
            time-periodic differential equations",
  journal= "SIAM J. Numer. Anal.",
  volume = "30",
  year   = "1993",
  pages  = "286--303"
  author = "Vandewalle, S. and Van Driessche, R. and Piessens, R.",
  title  = "The parallel performance of standard parabolic marching schemes",
  journal= "Int. J. High Speed Computing",
  volume = "3",
  year   = "1991",
  pages  =""1--29"


Date: Tue, 29 Jun 93 10:50:59 METDST
From: Kees Oosterlee (NW) 
Subject: Oosterlee references

C.W. Oosterlee and P. Wesseling,
A multigrid method for an invariant formulation of the incompressible
{N}avier-{S}tokes equations in general coordinates
Comm. Appl. Num. Methods, 8 (1992), pp. 721--734

C.W. Oosterlee and P. Wesseling,
A robust multigrid method for a discretization of the incompressible
{N}avier-{S}tokes equations in general coordinates
Impact Comp. Science and Eng., 5 (1993), pp. 128--151

C.W. Oosterlee and P. Wesseling,
A multigrid method for a discretization of the incompressible
{N}avier-{S}tokes equations in general coordinates
In: J.B. Vos, A. Rizzi, I.L. Ryhming (Eds.),
Proc. of the 9th GAMM Conf. on Num.  Meth. in Fluid Mech.,
Ser. Notes on Num. Fluid Mech., 35 (1992), pp. 99--106, Vieweg, Braunschweig

C.W. Oosterlee and P. Wesseling,
A robust multigrid method for a discretization of the incompressible
{N}avier-{S}tokes equations in general coordinates
In: Ch. Hirsch, J. Periaux, W. Kordulla (Eds.),
Proc. of the 1th Europ. Fluid Dyn. Conf., pp. 101--108, Elsevier,
Amsterdam (1992).


Date: Wed, 28 Jul 1993 13:09:01 -0400
From: (Craig Douglas)
Subject: More References

As noted in the last issue, I have been adding some more references to
mgnet/bib/mg.bib.  This is the promised second installment.  As always,
corrections and additions are always welcome.

A. C. Irving and  C. Michael
Finite size effects and scaling in lattice {CP$^{N 1}$},
Phys. Lett. B, 292 (1992), pp. 392-396

Iyengar and R. K. Satteluri and A. Goyal
Comparison of {S} and {V} cycles in multigrid method for linear elliptic
equations with variable coefficients,
Numer. Methods Partial Differential Equations, 8 (1992), pp. 113-125

Y. Jiang and C. P. Chen and P. K. Tucker
Multigrid solution of unsteady {N}avier {S}tokes equations using a pressure
Numer. Heat Transf. A, Appl., 20 (1991), pp. 81-93

T. Kalkreuter
Projective block spin transformations in lattice gauge theories,
Nucl. Phys. B, B376 (1992), pp. 637-660

G. King and F. C. Sze and P. Mak and T. A. Grotjohn and J. Asmussen
Ion and neutral energies in a multipolar electron cyclotron resonance
plasma source,
J. Vac. Sci. Technol. A, Vac. Surf. Films, 10 (1992), pp. 1265-1269

M. Kocvara
An algebraic study of a local multigrid method for variational
Appl. Math. Comput., 51 (1992), pp. 17-41

M. La~{S}cala and R. Sbrizzai and F. Torelli
A pipelined-in-time parallel algorithm for transient stability analysis,
IEEE Trans. Power Syst., 6 (1991), pp. 715-722

A. Lanza
Self gravitating thin disks around rapidly rotating black holes,
Astrophys. J., 389 (1992), pp. 141-156

M. L. Laursen and J. Smit and J. C. Vink
Multigrid updating of {U}(1) gauge fields,
Phys. Lett. B, 262 (1991), pp. 467-471

C. Liu and Z. Liu and S. F. McCormick
Multilevel adaptive methods for incompressible flow in grooved
J. Comput. Appl. Math., 38 (1991), pp. 283-295

J. C. Luo
Formulation of the finite element method by domain decomposition,
Comput. Struct., 43 (1992), pp. 751-760

R. Mattis and A. Haghighat
Domain decomposition of a two-dimensional {S$^n$} method,
Nucl. Sci. Eng., 111 (1992), pp. 180-196

D. J. Mavriplis
Three-dimensional unstructured multigrid for the {E}uler equations,
AIAA J., 30 (1992), pp. 1753-1761

D. J. Mavriplis
Turbulent flow calculations using unstructured and adaptive meshes,
Int. J. Numer. Methods Fluids, 13 (1991),  pp. 1131-1152

R. McLachlan
A steady separated viscous corner flow,
J. Fluid Mech., 231 (1991),  pp. 1-34

R. Meyer Spasche and B. Fornberg
Discretization errors at free boundaries of the {G}rad {S}chluter {S}hafranov
Numer. Math., 59 (1991), pp. 683-710

V. Mikulinsky
Multigrid treatment of thin domains,
SIAM J. Sci. Stat. Comput., 12 (1991), pp. 940-949

M. Napolitano
Efficient solution of two-dimensional steady separated flows,
Computers & Fluids, 20 (1991), pp. 213-222

C. W. Oehlrich and A. Quick
Performance evaluation of a communication system for transputer networks based
on monitored event traces,
Comput. Archit. News, 19 (1991), pp. 202-211

G. Palma
Renormalized loop expansion to compute finite size effects of the
constraint effective potential,
Z. Phys. C, Part. Fields, 54 (1992), pp. 679-682

G. W. Parker
What is the capacitance of parallel plates?,
Comput. Phys., 5 (1991), pp. 534-540

J. Peraire and J. Peiro and K. Morgan and O. Hassan and O. C. Zienkiewicz
Applications of supercomputers in aerodynamics,
Rev. Int. Metodos Numer. para Calc. Diseno Ing., 8 (1992), pp. 215-233

C. Y. Perng and R. L. Street
Coupled multigrid-domain-splitting technique for simulating incompressible
flows in geometrically complex domains,
Int. J. Numer. Methods Fluids, 13 (1991), pp. 269-286

A. L. Perkins
Tailored domain decomposition,
Adv. Eng. Softw., 14 (1992), pp. 145-149

T. von Petersdorff and E. P. Stephan
Multigrid solvers and preconditioners for first kind integral
Numer. Methods Partial Differential Equations, 8 (1992), pp. 443-450

G. Pini
Domain decomposition and nested grids in a parallel environment,
Supercomputer, 9 (1992), pp. 22-28

A. Plaza and L. Ferragut and R. Montenegro
Derefinement algorithms of nested meshes,
IFIP Trans. A, Comput. Sci. Technol., A12 (1992), pp. 409-415

W. H. Press and S. A. Teukolsky
Multigrid methods for boundary value problems {I},
Comput. Phys., 5 (1991), pp. 514-519

P. A. Rubini and H. A. Becker and E. W. Grandmaison and A. Pollard and
A. Sobiesiak and C. Thurgood
Multigrid acceleration of three dimensional, turbulent, variable
density flows,
Numer. Heat Transf. B, Fundam., 22 (1992), pp. 163-177

S. Sauter and G. Wittum
A multigrid method for the computation of eigenmodes of closed water
Impact Comput. Sci. Eng., 4 (1992), pp. 124-152

M. Schafer
Numerical solution of the time dependent axisymmetric {B}oussinesq
equations on processor arrays,
SIAM J. Sci. Stat. Comput., 13 (1992), pp. 1377-1393

J. N. Shadid and R. S. Tuminaro
Sparse iterative algorithm software for largescale {MIMD} machines: an
initial discussion and implementation,
Concurrency, Pract. Exp., 4 (1992), pp. 481-497

W. Shyy and M. E. Braaten and D. L. Burrus
Study of three-dimensional gas-turbine combustor flows,
Int. J. Heat Mass Transfer, 32 (1989), pp. 1155-1164

R. A. Smith and A. Weiser
Semicoarsening multigrid on a hypercube,
SIAM J. Sci. Stat. Comput., 13 (1992), pp. 1314-1329

G. Stoyan and R. Stoyan
Colouring the discretization graphs arising in the multigrid method,
Comput. Math. Appl., 22 (1991), pp. 55-62

R. C. Swanson and R. Radespiel
Cell centered and cell vertex multigrid schemes for the {N}avier-{S}tokes
AIAA J., 29 (1991), pp. 697-703

    Editor's Note: mgnet/bib/mg.bib has the BibTeX entries.  You, too, can
    -------------  have your published papers in there by just sending me
                   e-mail with the citations in any reasonable format.


Date: Fri, 30 Jul 93 13:04:44 EDT
From: worley@haven.EPM.ORNL.GOV (Pat Worley)
Subject: Paper on Parabolic Multigrid and Waveform Relaxation 

An Algorithm with Polylog Parallel Complexity for Solving Parabolic Partial
Differential Equations

Graham Horton (1)
Stefan Vandewalle (2)
Patrick Worley (3)


The standard numerical algorithms for solving parabolic partial differential
equations are inherently sequential in the time direction.  This paper
describes an algorithm for the time-accurate solution of certain classes of
parabolic partial differential equations that can be parallelized in both time
and space.  It has a serial complexity that is proportional to the serial
complexities of the best known algorithms.  The algorithm is a variant of the
multigrid waveform relaxation method where the scalar ordinary differential
equations that make up the kernel of computation are solved using a cyclic
reduction type algorithm.  Experimental results obtained on a massively
parallel multiprocessor are presented.

(1) Lehrstuhl f\"ur Rechnerstrukturen (IMMD 3), Universit\"at
Erlangen-N\"urnberg, Martensstrasse 3, D-8520 Erlangen, Federal Republic of
Germany.  E-mail:

(2) Department of Computer Science, Katholieke Universiteit Leuven,
Celestijnenlaan 200A, B-3001 Leuven (Heverlee), Belgium.  E-mail:

(3) Mathematical Sciences Section, Oak Ridge National Laboratory, P.O.  Box
2008, Oak Ridge, Tennessee 37831-6367, USA.  E-mail:

    Editor's Note: mgnet/papers/Horton_Vandewalle_Worley/mgwrcr.{dvi,ps}
    -------------  mgnet/papers/Horton_Vandewalle_Worley/mgwrcr.abstract


End of MGNet Digest