Send mail to:    mgnet@cs.yale.edu             for the digests or bakeoff
Current editor:  Craig Douglas                 douglas-craig@cs.yale.edu
Anonymous ftp repository:    ftp.ccs.uky.edu (128.163.209.106)

World Wide Web:  http://www.mgnet.org or
http://www.cerfacs.fr/~douglas/mgnet.html or
http://phase.etl.go.jp/mgnet or
http://www.ccs.uky.edu/mgnet

Today's editor:  Craig Douglas (douglas-craig@ccs.uky.edu)

Volume 8, Number 3 (approximately March 31, 1998)

Today's topics:

Job Open at Oxford
Postdoc position at CCMA of Penn State
PLTMG8.0
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.

See http://www.comlab.ox.ac.uk/oucl/jobs/pld.html

-------------------------------------------------------

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 (http://www.math.psu.edu/ccma/).
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 xu@math.psu.edu) 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
MGNet.

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
www.mgnet.org/mgnet-codes.html 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 http://etna.mcs.kent.edu. There is no charge to access ETNA, and all
ETNA articles are available in both PostScript and PDF formats.

-------------

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
conferences."

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

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: I.Duff@rl.ac.uk (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
England

Abstract

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/permute.ps.gz or
-------------  http://www.mgnet.org/mgnet-papers.html.

-------------------------------------------------------

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.

Sincerely,
Yvan Notay

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

<==========================================================>
> Yvan NOTAY                    |                          <
< Universite Libre de Bruxelles | email : ynotay@ulb.ac.be >
> 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     http://homepages.ulb.ac.be/~ynotay               >
>==========================================================<

Using approximate inverses in algebraic multilevel methods
----------------------------------------------------------

Y. Notay

http://homepages.ulb.ac.be/~ynotay
ftp://mnserver.ulb.ac.be/pub/reports/apinv.ps.gz
To appear in Numer. Math.

abstract
--------
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

http://homepages.ulb.ac.be/~ynotay
ftp://mnserver.ulb.ac.be/pub/reports/ganmn_ps/ganmn9702.ps.gz
Report GANMN 97-02

abstract
--------
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

http://homepages.ulb.ac.be/~ynotay
ftp://mnserver.ulb.ac.be/pub/reports/ganmn_ps/ganmn9705.ps.gz
Report GANMN 97-05

abstract
--------
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 www.mgnet.org/mgnet-conferences.html.  A list of
attendees and all of the abstracts can also be found there.

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
Constraints

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

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
Coefficients

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

------------------------------

End of MGNet Digest
**************************