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 8, Number 3 (approximately March 31, 1998)

Today's topics:

     Job Open at Oxford
     Postdoc position at CCMA of Penn State
     ETNA's Copper Mountain Proceedings.
     Paper by Duff and Koster
     3 Papers on Algebraic Multilevel Methods by Notay
     16 Papers added to 5th Copper Mountain Iterative Methods Area


From: "Mike Rudgyard" 
Date: Fri, 27 Mar 1998 14:15:12 +0000
Subject: Job Open at Oxford

If anyone is finishing their PhD/Post-doc, I have a post in parallel computing
(involving multigrid and distributed partitioning) here at Oxford.



Date: Fri, 27 Mar 1998 21:33:29 -0500
From: Jinchao Xu 
Subject: Postdoc position at CCMA of Penn State

Contingent upon final approval of funding, we will have a postdoc position
available from Fall 1998 in the Center for Computational Matheamtics and
Applications of Penn State University (
Applicants must have a strong background in numerical methods for partial
differential equations (especially finite element methods) and programming
experiences.  Good knowledge on multigrid methods is desirable.

Interested applicants should send application materials ASAP to 

        Professor Jinchao Xu
        Department of Mathematics
        Pennsylvania State University                 
        University Park, PA 16802             

Email applications (sent to are encouraged.  Email message
may include application materials or a letter indicating an URL address for
accessing other detailed application materials.

Penn State is an equal opportunity/affirmative action employer, and especially
encourages applications from women and minorities.


Date: Mon, 6 Apr 1998 13:33:13 -0700 (PDT)
From: "Randolph E. Bank" 
Subject: Pltmg8.0

PLTMG 8.0 is a package for solving elliptic partial differential equations in
general regions of the plane.  It is based on continuous piecewise linear
triangular finite elements, and features adaptive local mesh refinement,
multigraph iteration, and pseudo-arclength continuation options for parameter
dependencies.  The package includes an initial mesh generator and several
graphics packages.  Full documentation is provided in PLTMG:  A Software
Package for Solving Elliptic Partial Differential Equations - Users' Guide 8.0
(ISBN 0-89871-409-5), available from SIAM Publications.  PLTMG is provided as
Fortran (and a little C) source code, in both single and double precision
versions.  The included X-Windows GUI uses the default Athena Widget set, and
makes calls to standard library routines of the X-Windows system, which must
be loaded along with the PLTMG software.  PLTMG is available from Netlib and

    Editor's Note: The previous version (7.2) is still on MGNet, but will be
    -------------  deleted eventually.  You can find version 8.0 either in
          or in mgnet/Codes/pltmg.


Date: Fri, 13 Mar 1998 15:51:16 -0500
From: ETNA 
Subject: ETNA's Copper Mountain Proceedings.

The Editors of Electronic Transactions on Numerical Analysis, ETNA,
are proud to announce the publication of the Proceedings of the 
Eighth Copper Mountain Conference on Multigrid Methods held April 6-11,
1997, at the Copper Mountain Resort in Colorado, as a special issue of ETNA .
This issue, Volume 6, contains 290 pages of 19 high-quality articles dealing
with multigrid and other multilevel techniques. ETNA can be found on the web
at URL There is no charge to access ETNA, and all
ETNA articles are available in both PostScript and PDF formats.

    Editor's Note:  Here is what you find for the table of contents:

                    Special Issue on Multilevel Methods

This is a special issue of ETNA on multilevel methods for numerical solution
of partial differential equations and other complex mathematical problems.
The papers here consist of results presented at the Eighth Copper Mountain
Conference on Multigrid Methods held April 6-11, 1997, at Copper Mountain
Resort in Colorado. There were 60 talks at the meeting, counting special
workshop and circus sessions, with about 100 attendees. To quote the MGNet
'Postcard' from Craig Douglas:

"For the first time in years, there were no parallel sessions for talks,
giving the conference the type of intimacy found in the GAMM parallel
multigrid workshops held in Germany for many years and most recently in
Austria. Two years ago there were many newcomers to the Copper Mountain
conference. Once again this was the case. In part this is due to the large
number of graduate students and fresh Ph.D.'s who have attended both

The conference series continues to reflect the maturation of the multigrid
field. There were many talks on basic theory and algorithms, important
practical applications, parallelization, and other computational issues. The
papers in this special issue illustrate this evolution, but they also
suggested the seemingly endless number of research questions that remain.

Each of the following papers was subjected to a critical refereeing process,
upholding the high standards of the ETNA editorial board. We extend our
sincerest thanks to following members of our Conference Committee who served
as guest editors for this special issue:

 Joel Dendy     Los Alamos National Lab
 Craig Douglas  University of Kentucky
 Van Henson     Lawrence Livermore National Lab
 Jim Jones      Lawrence Livermore National Lab
 Kirk Jordan    IBM
 Duane Melson   NASA Langley Research Center
 Seymour Parter University of Wisconsin
 Joseph Pasciak Texas A & M
 John Ruge      University of Colorado at Boulder
 Irad Yavneh    Technion

We also wish to thank the University of Colorado, the Society for Industrial
and Applied Mathematics, and the Institute for Algorithms and Scientific
Computing of the GMD for organizational support. Finally, we are especially
indebted to Fred Howes of the Department of Energy, Michael Steuerwalt of
the National Science Foundation, Kirk Jordan of IBM, and Ulrich Trottenberg
of the Institute for Algorithms and Scientific Computing of the GMD for
financial support.

    Steve McCormick and Tom Manteuffel, University of Colorado, Boulder

The Gauss Center Research in Multiscale Scientific Computation             1
 Achi Brandt

Local Error Estimates and Adaptive Refinement for First-Order
System Least Squares (FOSLS)                                              35
 Markus Berndt, Thomas A. Manteuffel, and Stephen F. McCormick

Experiences With Negative Norm Least-Square Methods for the
Navier-Stokes Equations                                                   44
 P. Bochev

A Multigrid Algorithm for Higher Order Finite Elements on Sparse
Grids                                                                     63
 Hans-Joachim Bungartz

The Analysis of Intergrid Transfer Operators and Multigrid
Methods for Nonconforming Finite Elements                                 78
 Zhangxin Chen

Semicoarsening Multigrid for Systems                                      97
 J.E. Dendy, Jr.

Multigrid Algorithm with Conditional Coarsening for the
Non-aligned Sonic Flow                                                   106
 Boris Diskin

A Comparison of Multilevel Adaptive Methods for Hurricane Track
Prediction                                                               120
 Scott R. Fulton

Multigrid Method for H(DIV) in Three Dimensions                          133
 R. Hiptmair

Asymptotic Stability of a 9-Point Multigrid Algorithm for
Convection-Diffusion Equations                                           153
 Jules Kouatchou

Wave-Ray Multigrid Method for Standing Wave Equations                    162
 A. Brandt and I. Livshits

Directional Coarsening and Smoothing for Anisotropic
Navier-Stokes Problems                                                   182
 Dimitri J. Mavriplis

A Two-level Discretization Method for the Stationary MHD
Equations                                                                198
 W. J. Layton, A. J. Meir, and P. G. Schmidt

A Stable Multigrid Strategy for Convection-Diffusion Using High
Order Compact Discretization                                             211
 Anand L. Pardhanani, William F. Spotz, and Graham F. Carey

A Parallel Multigrid Method Using the Full Domain Partition              224
 William F. Mtichell

A Multigrid Smoother for High Reynolds Number Flows                      234
 Erik Sterner

Fast Solution of MSC/NASTRAN Sparse Matrix Problems Using A
Multilevel Approach                                                      246
 C. A. Thole, S. Mayer, and A. Supalov

A Comparison of Multilevel Methods for Total Variation
Regularization                                                           255
 P. S. Vassilevski and J. G. Wade

Krylov Subspace Acceleration For Nonlinear Multigrid Schemes             271
 T. Washio and C. W. Oosterlee


Date: Sun, 8 Mar 1998 21:09:07 GMT
From: (Iain Duff)
Subject: Paper by Duff and Koster

     The Design and Use of Algorithms for Permuting Large Entries to the
                         Diagonal of Sparse Matrices

                   Iain S. Duff and Jacko Koster

                  Department of Computation and Information
                                 Atlas Centre
                        Rutherford Appleton Laboratory
                                Oxon OX11 0QX


We consider techniques for permuting a sparse matrix so that the diagonal of thepermuted matrix has entries of large absolute value.  We discuss various
criteria for this and consider their implementation as computer codes.
We then indicate several cases where such a permutation can be useful.  These
include the solution of sparse equations by a direct method and by an
iterative technique.  We also consider its use in generating a preconditioner
for an iterative method. We see that the effect of these reorderings can be
dramatic although the best {\it a priori} strategy is by no means clear.

    Editor's Note: in mgnet/papers/Duff-Koster/ or


Date: Thu, 2 Apr 1998 12:45:17 +0200 (MET DST)
From: Yvan NOTAY 
Subject: 3 Papers on Algebraic Multilevel Methods by Notay

I recently wrote 3 papers on algebraic multilevel methods.  Title, abstract
and ftp & http references are given below.

I suggest you to include this in the next MG-Digest, and I further encourage
you to download the files, so as to make them available on the MGNet preprint
service too.

Many thanks in advance.
    Yvan Notay

    Editor's Note: Uploaded to MGNet; see
    -------------  The files are in mget/papers/Notay.

 > Yvan NOTAY                    |                          <
 < Universite Libre de Bruxelles | email : >
 > Service de Metrologie         |                          <
 <            Nucleaire (CP 165) | tel : (32) 2  650 36 70  >
 > 50 av. F.D.Roosevelt          | fax : (32) 2  650 45 34  <
 < B-1050 Bruxelles  BELGIUM     |                          >
 < URL               >

Using approximate inverses in algebraic multilevel methods

Y. Notay
To appear in Numer. Math.

This paper deals with the iterative solution of large sparse symmetric
positive definite systems.  We investigate preconditioning techniques of the
two-level type that are based on a block factorization of the system matrix.
Whereas the basic scheme assumes an exact inversion of the submatrix related
to the first block of unknowns, we analyze the effect of using an approximate
inverse instead.  We derive condition number estimates that are valid for any
type of approximation of the Schur complement and that do {\em not} assume the
use of the hierarchical basis.  They show that the two-level methods are
stable when using approximate inverses based on modified ILU techniques, or
explicit inverses that meet some row-sum criterion.  On the other hand, we
bring to the light that the use of standard approximate inverses based on
convergent splittings can have a dramatic effect on the convergence rate.
These conclusions are numerically illustrated on some examples.

Optimal order preconditioning of finite difference matrices

Yvan Notay
Report GANMN 97-02

A new multilevel preconditioner is proposed for the iterative solution of two
dimensional discrete second order elliptic PDEs.  It is based a recursive
block incomplete factorization of the system matrix partitioned in a
two-by-two block form, in which the submatrix related to the first block of
unknowns is approximated by a MILU(0) factorization, and the Schur complement
computed from a diagonal approximation of the latter submatrix.

It is shown that this technique, combined with a simple $W$ cycle scheme,
leads to optimal order preconditioning of five point finite difference
matrices.  This result holds independently of possible anisotropy or jumps in
the PDE coefficients as long as the latter are piecewise constant on the
coarsest mesh.  Numerical results illustrate the efficiency and the robustness
of the proposed method.

Optimal V cycle algebraic multilevel preconditioning

Y. Notay
Report GANMN 97-05

We consider algebraic multilevel preconditioning methods based on the
recursive use of a $2 \times 2$ block incomplete factorization procedure in
which the Schur complement is approximated by a coarse grid matrix.  As is
well known, for discrete second order elliptic PDEs, optimal convergence
properties are proved for such basic two-level schemes under mild assumptions
on the PDE coefficients, but their recursive use in a simple V cycle algorithm
does generally not lead to optimal order convergence.

In the present paper, we analyze the combination of these techniques with a
smoothing procedure much similar to the one used in standard multigrid
algorithms, except that smoothing is not required on the finest grid.
Theoretical results prove optimal convergence properties for the V cycle under
an assumption similar to the ``approximation property" of the classical
multigrid convergence theory.  On the other hand, numerical experiments show
that, for both 2D and 3D problems, using rather simple smoothing strategies
suffices to make the condition number close to that of the two-level method.


Date: Tue, 31 Mar 1998 12:31:11 -0500
From: Craig Douglas 
Subject: 16 Papers added to 5th Copper Mountain Iterative Methods Area

The following papers or (roughly) 7 page extended abstracts were added to the
virtual proceedings of the Fifth Copper Mountain Iterative Methods Conference.
They can be found through  A list of
attendees and all of the abstracts can also be found there.

  M. Adams
  A Parallel Maximal Independent Set Algorithm

  A. Brandt, M. Israeli, I. Yavneh, and A. Siegel
  Multigrid Solution of an Elliptic Boundary-Value Problem with Integral

  R. Bridson and W.-P. Tang
  Ordering for the Factored Approximate Inverse Preconditioners

  W. K. Ching
  Circulant Approximation for Preconditioning in Stochastic Automata Networks

  T. Dayar and W. J. Stewart
  Comparison of Partitioning Techniques for Two-Level Iterative Solvers on
  Large, Sparse Markov Chains

  D. S. Daoud and T. Gungormus
  On the Schwarz Alternating Procedure with a Polynomial Preconditioning
  Conjugate Gradient

  A. Knyazev
  Preconditioned Eigensolvers - an Oxymoron?

  D. Loghin
  Green's Functions For Preconditioning

  W.-S.  Luk, J. Janssen, and S. Vandewalle
  Application of determinant Maximization Programming to the SOR and Chebyshev
  Methods for Complex Linear Systems

  S. Oliveira
  Convergence and Parallelization of a Preconditioned Algorithm for Eigenvalues

  J. Rahola
  Iterative Solution of Dense Linear Systems

  A. C. Robinson and M. A. Christon
  Using AZTEC to Solve the Linear System Associated with the Three-dimensional
  Magnetohydrodynamic (MHD) Modeling in ALEGRA

  M. Seaid
  A Fast Monotone Iterative Method for Nonlinear Reaction-Diffusion Systems

  Y. Shapira
  A Multi-Level Method for Sparse Linear Systems

  H. Van der Vorst
  Preconditioning for Eigenproblems

  C. Vuik, G. Segal, and K. Meijerink
  An Efficient CG Method for Layered Problems with Large Contrasts in the

    Editor's Note: Files in mgnet/Conferences/CMCIM98.


End of MGNet Digest