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

World Wide Web: or

Today's editor:  Craig Douglas (

Volume 5, Number 4 (approximately April 30, 1995)

Today's topics:

     Change of URL for Marcus Speh's Multigrid Algorithm Library
     MGNet papers of Z. Cai, T. A. Manteuffel, and S. F. McCormick
     List of Copper Mountain 95 Papers/Abstracts
     International Linear Algebra Year at CERFACS
     ICCI95 (Int. Conf. Control & Info. Hong Kong)
     Some Recent Bibliography Additions


Date:   Mon, 10 Apr 1995 21:46:12 +0200 (MESZ)
From: Ulrich Ruede 
Subject: Change of URL for Marcus Speh's Multigrid Algorithm Library

The Multigrid Algorithm Library on the World Wide Web, formerly maintained by
Marcus Speh at DESY in Hamburg, with URL 


has been updated and moved to Technische Universitaet Muenchen.  It is now
accessible at URL


The page provides access to various multigrid related information, including
references, preprints, and conferences.  Please update existing links to the
new location.


Date: Thu, 27 Apr 1995 13:08:44 -0600
From: (steve mccormick)
Subject: MGNet papers of Z. Cai, T. A. Manteuffel, and S. F. McCormick

    Editor's Note: Steve sent 3 papers to MGNet.  They are in the directory
    -------------  mgnet/papers/CaiZ-Manteuffel-McCormick.  Steve promises
                   more papers in May.


                                    Z. Cai
                                  R. Lazarov
                               T. A. Manteuffel
                               S. F. McCormick


This paper develops ellipticity estimates and discretization error bounds for
elliptic equations (with lower order terms) that are reformulated as a
least-squares problem for an equivalent first-order system.  The main result
is the proof of ellipticity, which is used in a companion paper to establish
optimal convergence of multiplicative and additive solvers of the discrete

    Editor's Note: in mgnet/papers/CaiZ_Manteuffel_McCormick/elliptic1.abs
    -------------  and mgnet/papers/CaiZ_Manteuffel_McCormick/


                                    Z. Cai
                               T. A. Manteuffel
                               S. F. McCormick


This paper develops a least-squares functional that arises from recasting
general second-order uniformly elliptic partial differential equations in 
n = 2 or 3 dimensions as a system of first-order equations.  In part I [11] a
similar functional was developed and shown to be elliptic in the H(div)xH^1
norm and to yield optimal convergence for finite element subspaces of
H(div)xH^1.  In this paper the functional is modified by adding a compatible
constraint and imposing additional boundary conditions on the first-order
system.  The resulting functional is proved to be elliptic in the (H^1)^{n+1}
norm.  This immediately implies optimal error estimates for finite element
approximation by standard subspaces of (H^1)^{n+1}.  Another direct
consequence of this ellipticity is that multiplicative and additive multigrid
algorithms applied to the resulting discrete functionals are optimally
convergent.  As an alternative to perturbation based approaches, the
least-squares approach developed here applies directly to
convection-diffusion-reaction equations in a unified way and also admits a
fast multigrid solver, historically a missing ingredient in least-squares

    Editor's Note: in mgnet/papers/CaiZ_Manteuffel_McCormick/elliptic2.abs
    -------------  and mgnet/papers/CaiZ_Manteuffel_McCormick/


                                    Z. Cai
                               T. A. Manteuffel
                               S. F. McCormick


Following our earlier work on general second-order scalar equations, here we
develop a least-squares functional for the two- and three-dimensional Stokes
equations, generalized slightly by allowing a pressure term in the continuity
equation.  By introducing a velocity flux variable and associated curl and
trace equations, we are able to establish ellipticity in an H^1 product norm
appropriately weighted by the Reynolds number.  This immediately yields
optimal discretization error estimates for finite element spaces in this norm
and optimal algebraic convergence estimates for m ultiplicative and additive
multigrid methods applied to the resulting discrete systems.  Both estimates
are uniform in the Reynolds number.  Moreover, our pressure-perturbed form of
the generalized Stokes equations allows us to develop an analogous result for
the Dirichlet problem for linear elasticity, with estimates that are uniform
in the Lam{\'e} constants.

    Editor's Note: in mgnet/papers/CaiZ_Manteuffel_McCormick/stokes.abs
    -------------  and mgnet/papers/CaiZ_Manteuffel_McCormick/


Date:   Sun, 30 Apr 1995 11:11:11 -0400 (EST)
From: Craig Douglas 
Subject: List of Copper Mountain 95 Papers/Abstracts

On MGNet, in the mgnet/Conferences/CopperMtn95 directory are numerous papers
from the conference, held during April 2-7.  The papers are mostly gzipped
PostScript files.  The abstracts are mostly in plain text in the Abstracts
subdirectory.  Attendees should update their papers as they revise them for
the forthcoming printed proceedings.

What is currently there is the following:

Loyce Adams
A multigrid algorithm for immersed interface problems

Eyal Arian and Shlomo Ta'asan
Smoothers for optimization problems

Dana M. Bedivan
A finite element method for inhomogeneous problems using a multigrid algorithm
for eliminating the boundary condition

M. Berndt and K. Witsch
Multigrid With Overlapping Patches

P. Bochev, Z. Cai, T. A. Manteuffel, and  S. F. McCormick
First-order system least squares for the Navier-Stokes equations

James Bordner and Faisal Saied
MGLab:  An Interactive Environment for Multigrid Methods

A. Borz\`{\i}, K.W.  Morton, E. S\"uli and M. Vanmaele
A full multi-grid method for the solution of the cell vertex finite volume
Cauchy--Riemann equations

J. H. Bramble, J. E. Pasciak, and A. T. Vassilev
Analysis of the inexact Uzawa algorithm for saddle point problems

A. Brandt and L. Zaslavsky
Multilevel algorithm for atmospheric data assimilation

Jan Broeze, Bernard Geurts, Hans Kuerten, Mand artin Streng
Multigrid acceleration of time-accurate DNS of compressible turbulent flows

Z. Cai, T. A. Manteuffel, and S. F. McCormick
First-order system least squares for the Stokes equations, with application to
linear elasticity

Mario Casarin
Quasi-optimal Schwarz methods for the conforming spectral element

Zhangxin Chen and Richard E. Ewing
Recent development of multigrid algorithms for mixed and nonconforming methods
for second order elliptic problems

M. B. Davis and G. F. Carey
Parallel element-by-element spectral multilevel techniques for finite elements

J. E. Dendy, Jr.
Revenge of the semicoarsening frequency decomposition multigrid method

Qingping Deng
An optimal order nonnested mixed multigrid method for generalized Stokes

Craig C. Douglas, Jim Douglas, Jr., and David E. Fyfe
A Unified Multigrid Theory for Non-Nested Grids and/or Quadrature

Eugene G. D'yakonov
Effective numerical methods for solving elliptic problems in strengthened
Sobolev spaces

Peter Eliasson and Bj\"{o}rn Engquist
The effects of dissipation and coarse grid resolution for multigrid in flow

Howard C. Elman
Multigrid and Krylov subspace methods for the discrete Stokes equations

Thor Gjesdal
A cell-centred multigrid algorithm for all grid sizes

W. L. Golik
Numerical study of multigrid methods with various smoothers for the elliptic
grid generation equations

Herve Guillard
Some aspects of multigrid methods on non-structured meshes

Mike Holst and Stefan Vandewalle
Schwarz methods:  to symmetrize or not to symmetrize

Hong Wang
An ELLAM-based domain decomposition and local refinement algorithm for
second-order hyperbolic equations with interfaces

Jim E. Jones
A mixed finite volume element method for flow calculations in porous media

M. Jung and U. Ruede
Implicit extrapolation methods for variable coefficient problems

R. Jyotsna and S. P. Vanka
A pressure based multigrid procedure for the Navier-Stokes on unstructured

Hwar-Ching Ku and Aleksander S. Popel
The multigrid-mask numerical method for solution of incompressible
Navier-Stokes equations

Chen-Y ao G. Lai
Implementation of hybrid V-cycle algebraic multilevel methods for mixed finite
element systems with penalty

Chang-Ock Lee
Multigrid methods for the pure traction problem of linear elasticity:  mixed

Chaoqun Liu and Zhining Liu
Multiple scale simulation for transitional and turbulent flow

Serguei Maliassov
Multilevel substructuring preconditioning of nonconforming finite element
approximations of second order elliptic problems

Jan Mandel and Radek Tezaur  
Convergence of a substructuring method with Lagrange multipliers

T. A. Manteuffel, S. F. McCormick, and G. Starke
First order system least-squares for second-order elliptic problems with
discontinuous coefficients

Thomas A. Manteuffel and Klaus J. Ressel
Least-squares finite-element solution of the neutron transport equation in
diffusive regimes

A. J. Meir
On DGS relaxation: the Stokes problem

N. Duane Melson and Mark D. Sanetrik
Multigrid acceleration of time-accurate Navier-Stokes calculations

H. Molenaar
Multigrid methods for fully implicit black-oil reservoir simulation

E. Morano, D. Mavriplis, and V. Venkatakrishnan
Coarsening strategies for unstructured multigrid techniques with applications
to anisotropic problems

S. V. Nepomnyaschikh
Preconditioning operators on unstructured grids

Elyas Nurgat and Martin Berzins
Multigrid methods for EHD problems

Suely Oliveira
Multigrid and Krylov subspace methods for transport equations:  absorption

Mary Ellen Oman
Fast multigrid techniques in total variation-based image reconstruction

Christoph Pflaum
A multi-level-algorithm for the solution of second order elliptic differential
equations on sparse grids

J. R. Phillips
Error and complexity analysis for a collocation-grid-projection plus
precorrected-FFT algorithm for solving potential integral equations with
Laplace or Helmholtz kernels

Yair Shapira
Analysis of red-black relaxation in multigrid

Yair Shapira
Multigrid techniques for highly indefinite equations

A. Stathopoulos, Y. Saad, and C. F. Fischer
A Schur complement method for eigenvalue problems

Petr Van\v{e}k, Jan Mandel, and Marian Brezina
Algebraic multigrid by smoothed aggregation for second and fourth order
elliptic problems

C. Vuik, P. Wesseling, and S. Zeng
Krylov subspace and multigrid methods applied to the incompressible 
Navier-Stokes equations 

R. Webster
An algebraic multigrid solver for the Navier-Stokes problems in the discrete
second-order approximation

Shengyou Xiao and David Young
Multiple coarse grid multigrid methods for solving elliptic problems

Dexuan Xie
New nonlinear multigrid analysis

Jinchao Xu
The auxiliary space method and optimal multigrid preconditioning techniques
for unstructured grids

Xiaoqing Zheng, Chaoqun Liu, Changming Liao, Zhining Liu, and S. F. McCormick
Multigrid method for modeling multi-dimensional combustion with detailed


Date: Fri, 28 Apr 1995 18:41:50 +0200
Subject: International Linear Algebra Year at CERFACS

As announced in our previous message, information about the International
Linear Algebra Year is now available on WWW.  Our home page is
You will find informations about the workshops, the registration, the
accomodation, the visitor programme ...  There will soon be detailed
programmes for the first two workshops with the possibility of reading and
downloading the available abstracts.
For those of you who may have trouble in accessing WWW, the same information
is accessible via anonymous ftp. Our server is (
The directory /pub/algo/workshops/ILAY/Info contains the postscript versions
of the information available through WWW.
Requests for further information should be made to
We remind you of the main information about ILAY.
September 26-29   Direct methods
October   17-20   Eigenvalues and beyond
April     22-25   Optimization and linear algebra
June      11-14   Iterative methods
The two workshops in 1995 will be held at the UNESCO Centre in Toulouse.
Each three-day workshop will be preceded by a tutorial or industrially
oriented first day.  Because of support, we are able to keep the cost to 1500
FFR (for registration, documentation, lunches, teas and coffees) for the
three-day workshop and tutorial, with a reduction to 1000 FFR for full-time
students, and a fee of 3000 FFR for non-academics.

Living costs in the Toulouse region are quite low, normally about 250FFR per
day for bed, breakfast and evening meal.  Reduced price accommodation is
available at UNESCO.

    Editor's Note: There will be domain decomposition and multigrid days
    -------------  during the Iterative methods workshops.


Date: Mon, 1 May 95 19:10:52 -0600
From: Floyd Hanson 
Subject: ICCI95 (Int. Conf. Control & Info. Hong Kong)

ICCI95 will be held 5-9 June 1995, The Institute of Mathematical Sciences,
Chinese University of Hong Kong, Shatin NT, Hong Kong.  Technical Co-Sponsored
by the IEEE Control System Society and the IEEE Robotics and Automation
Society.  The Conference will include invited keynote speakers, contributed
sessions and invited minisymposia, in broad areas of automatic control, system
theory, information theory and applications.  Keynote Invited Speakers:  Jian
Song, Jagdish Chandra, Eugene Wong, Y.-C. Larry Ho, S. K. Mitter, J. C.
Willems, B. A. Francis, B. D. O. Anderson and Suguru Arimoto.  Minisymposia:
Integrated Design for High Performance Systems, Parallel and Related Methods
in Control, and Stochastic Theory-Adaptive Control.  There are about 15
contributed sessions.  The conference is also sponsored by the US Army
Research Office, the Army Research Office-Far East, US Office of Naval
Research, the K. C. Wong Education Foundation, the American GNC Corporation,
Varitronix Limited, Hong Kong Baptist University, as well as other
foundations.  the Institute of Mathematical Sciences of the Chinese University
of Hong Kong is the host of the conference.  For local information, advance
program, or registration forms can be found by Anonymous FTP using:  ftp; login:  anonymous; password:  ``your-email-address''; cd
/conf/icci95; get program.tex; get local-info.tex; get regis.frm; quit.  For
more information, contact:  Dr.  Kung Fu Ng, ICCI95 Local Arrangements
Committee, Department of Mathematics, Chinese University of Hong Kong Shatin
NT, Hong Kong, E-mail:


Date: Mon, 1 May 1995 15:57:44 -0400
From: (Craig Douglas)
Subject: Some Recent Bibliography Additions


{\sc R.~E. Bank, J.~Mandel, and S.~F. McCormick}, {\em Variational multigrid
  theory}, in Multigrid Methods, SIAM, Philadelphia, 1985, pp.~131--178.

{\sc C.~Bennet and R.~Sharpley}, {\em Interpolation of Operators}, Academic
  Press, New York, 1988.

{\sc C.~Bernardi and Y.~Maday}, {\em Approximations spectrales de probl{\`e}mes
  aux limites elliptiques}, vol.~Math{\`e}matiques \& Applications,
  Springer--Verlag, Paris, 1992.

{\sc J.~H. Bramble, J.~E. Pasciak, and J.~Xu}, {\em A multilevel preconditioner
  for domain decomposition boundary systems}, in Proceedings of the Tenth
  International Conference on Computer Methods in Applied Science and
  Engineering, New York, 1992, Nova Sciences.

{\sc J.~H. Bramble and J.~Xu}, {\em A local post--processing technique for
  improvising the accuracy in mixed finite element approximations}, SIAM J.
  Numer. Anal., 24 (1989), pp.~1267--1275.

{\sc A.~Brandt and A.~A. Lubrecht}, {\em Multilevel matrix multiplication and
  fast solution of integral equations}, J. Comp. Phys., 90 (1990),

{\sc S.~C. Brenner}, {\em A nonconforming mixed multigrid method for the pure
  traction problem in planar linear elasticity}, Math. Comp., 63 (1994),
  pp.~435--460 and S1--S5.

{\sc S.~C. Brenner and L.~R. Scott}, {\em The Mathematical Theory of Finite
  Element Methods}, Texts in Applied Mathematics, Springer--Verlag, New York,

{\sc H.-J. Bungartz}, {\em An adaptive {P}oisson solver using hierarchical
  bases and sparse grids}, in Proceedings of the IMACS International Symposium
  on Iterative Methods in Linear Algebra, Brussels, April, 1991, Amsterdam,
  1992, Elsevier.

{\sc T.~F. Chan}, {\em Domain decomposition algorithms and computational fluid
  dynamics}, in Vector and Parallel Computing: issues in applied research and
  development, Ellis Horwood Ltd. (J. Wiley \& Sons), Chichester, 1989,

{\sc Z.~Chen}, {\em Analysis of mixed methods using conforming and
  nonconforming finite element methods}, RAIRO, Math. Mod. Num. Anal., 27
  (1993), pp.~9--34.

{\sc C.~C. Douglas, J.~Douglas, and D.~E. Fyfe}, {\em A multigrid unified
  theory for non-nested grids and/or quadrature}, E. W. J. Numer. Math., 2
  (1994), pp.~285--294.

{\sc C.~C. Douglas, A.~Ern, and M.~D. Smooke}, {\em Numerical simulation of
  laminar diffusion flames}, SIAM News, 27 (1994), pp.~1, 12--13, 17.

{\sc J.~B. Drake and L.~J. Gray}, {\em Parallel implementation of the boundary
  element method}, in Vector and Parallel Computing: issues in applied research
  and development, Ellis Horwood Ltd. (J. Wiley \& Sons), Chichester, 1989,

{\sc M.~Dryja, B.~F. Smith, and O.~B. Widlund}, {\em Schwarz analysis of
  iterative substructuring algorithms for elliptic problems in three
  dimensions}, SIAM J. Numer. Anal., 31 (1994).

{\sc M.~Dryja and O.~B. Widlund}, {\em Domain decomposition algorithms with
  small overlap}, SIAM J. Sci. Comput., 15 (1994), pp.~604--620.

{\sc T.~F. Dupont, R.~P. Kendall, and H.~H. Rachford}, {\em An approximate
  factorization procedure for solving self--adjoint elliptic difference
  equations}, SIAM J. Numer. Anal., 5 (1968), pp.~559--573.

{\sc R.~E. Ewing}, {\em Large scale computing in reservoir simulation}, in
  Vector and Parallel Computing: issues in applied research and development,
  Ellis Horwood Ltd. (J. Wiley \& Sons), Chichester, 1989, pp.~123--137.

{\sc R.~E. Ewing, Yu. Kuznetsov, R.~Lazarov, and S.~Maliassov}, {\em
  Preconditioning of nonconforming finite element approximations of second
  order elliptic problems}, in Proc. of the Third Int. Conf. on Advances in
  Numerical Methods and Applications, Bulgaria, 1994, pp.~101--110.

{\sc W.~D. Gropp, E.~Lusk, and A.~Skjellum}, {\em Using MPI: Portable Parallel
  Programming with the Message-Passing Interface}, Scientific and Engineering
  Computation, MIT Press, Cambridge, MA, 1994.

{\sc V.~E. Henson}, {\em Parallel compact symmetric ffts}, in Vector and
  Parallel Computing: issues in applied research and development, Ellis Horwood
  Ltd. (J. Wiley \& Sons), Chichester, 1989, pp.~153--164.

{\sc Y.~Maday, D.~Meiron, A.~T. Patera, and E.~M. R{\o}nquist}, {\em Analysis
  of iteratifve methods for steady and unsteady {S}tokes problem: {A}pplication
  of spectral element discretization}, SIAM J. Sc. Comp., 14 (1993),

{\sc M.~E.~G. Ong}, {\em The {3D} linear hierarchical basis preconditioner and
  its shared memory parallel implementation}, in Vector and Parallel Computing:
  issues in applied research and development, Ellis Horwood Ltd. (J. Wiley \&
  Sons), Chichester, 1989, pp.~273--283.

{\sc S.~S. Pahl}, {\em Schwarz type domain decomposition methods for spectral
  element discretizations}, Master's thesis, University of Witwatersrand,
  Johannesburg, South Africa, 1993.

{\sc J.~E. Pasciak}, {\em Domain decomposition preconditioners for elliptic
  problems in two and three dimensions}, in Numerical Algorithms for Modern
  Parallel Computer Architectures, IMA Volumes Math. Appl., Springer--Verlag,
  New York, 1988, pp.~163--172.

{\sc L.~F. Pavarino}, {\em Domain decomposition algorithms for the p--version
  finite element mehtod for elliptic problems}, PhD thesis, New York
  University, New York, 1992.

\leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Additive {S}chwarz
  methods for the p--version finite element method}, Numer. Math., 66 (1994),

\leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Schwarz methods with
  local refinement for the p-version finite element method}, Numer. Math., 69
  (1994), pp.~185--211.

{\sc L.~F. Pavarino and O.~B. Widlund}, {\em Iterative substructuring methods
  for spectral elements in three dimensions}, in The finite element method:
  fifty years of the Courant element, Marcel Dekker, New York, Basel, Hong
  Kong, 1994, pp.~345--355.

\leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Preconditioned
  conjugate gradient solvers for spectral elements in 3{D}}, in Solution
  Techniques for Large-Scale {CFD} Problems, John Wiley \& Sons, New York,
  1995, pp.~189--210.

{\sc C.~Pflaum}, {\em Anwendung von {M}ehrgitterverfahren auf d{\"u}nnen
  {G}ittern}, PhD thesis, Technische Universit{\"a}t M{\"u}nchen, Munich, 1992.

{\sc A.~Reusken}, {\em Convergence of the multigrid full approximation scheme
  for a class of elliptic mildly nonlinear boundary value problems}, Numer.
  Math., 52 (1988), pp.~251--277.

\leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em Convergence of the
  multigrid full approximation scheme including the {V}--cycle}, Numer. Math.,
  53 (1988), pp.~663--686.

{\sc L.~R. Scott and S.~Zhang}, {\em Higher--dimensional nonnested multigrid
  methods}, Math. Comp., 58 (1992), pp.~457--466.

{\sc R.~Verf{\"u}rth}, {\em Multi--level algorithms for mixed probelms {II}.
  {T}reatment of the mini--element}, SIAM J. Numer. Anal., 25 (1988),

\leavevmode\vrule height 2pt depth -1.6pt width 23pt, {\em A posteriori error
  estimates for the {S}tokes equations {II} non--conforming discretizations},
  Numer. Math., 60 (1991), pp.~235--249.

{\sc T.~von Petersdorff and E.~P. Stephan}, {\em On the convergence of the
  multigrid method for a hypersingular integral equation of the first kind},
  Numer. Math., 57 (1990), pp.~379--391.

{\sc D.~Xie}, {\em Nonlinear multigrid analysis for a mildly elliptic nonlinear
  boundary value problems}, PhD thesis, U. of Houston, Houston, 1995.

{\sc C.~Zenger}, {\em Sparse grids}, in Paralle algorithms for partial
  differential equations: Proceedings of the Sixth GAMM-Seminar, Kiel, Jan.
  1990, vol.~Notes on Numerical Fluid Mechanics, vol. 31, Vieweg, Braunschweig,



End of MGNet Digest