Send mail to:  mgnet@cs.yale.edu             for the digests or bakeoff
               mgnet-requests@cs.yale.edu    for comments or help
 
Anonymous ftp repository:  www.mgnet.org (128.163.209.19)
 
Current editor:  Craig Douglas douglas-craig@cs.yale.edu
 

World Wide Web:  http://www.mgnet.org or
                 http://casper.cs.yale.edu/mgnet/www/mgnet.html or
                 http://www.cerfacs.fr/~douglas/mgnet.html or
                 http://phase.etl.go.jp/mgnet or
                 http://www.nchc.gov.tw/RESEARCH/Math/mgnet/www/mgnet.html

Today's editor:  Craig Douglas (douglas-craig@cs.yale.edu)

Volume 10, Number 7 (approximately July 31, 2000)

Today's topics:

     New Book (Briggs, Henson, McCormick)
     Book on Multilevel Methods in Lubrication
     Half Injection and Full weighting in RBGS Smoothing
     AMG Presentation at Strobl - Commentary
     AMG Presentation at Strobl - Wagner
     AMG Presentation at Strobl - Stueben
     AMG Presentation at Strobl - Reitzinger
     AMG Presentation at Strobl - Pasciak
     AMG Presentation at Strobl - Kraus
     AMG Presentation at Strobl - Jones

Greetings from Hsinchu (NCHC)!

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

Date: Wed, 19 Jul 2000 18:26:57 -0600
From: Steve McCormick 
Subject: New Book

A Multigrid Tutorial
Second Edition
William L. Briggs, Van Emden Henson, Steve F. McCormick

The book updates the five chapters of Briggs's original "A Multigrid Tutorial"
and includes new material in five additional chapters.

Contents

    Preface to the Second Edition
    Preface to the First Edition
    Chapter 1: Model Problems
    Chapter 2: Basic Iterative Methods
    Chapter 3: Elements of Multigrid
    Chapter 4: Implementation
    Chapter 5: Some Theory
    Chapter 6: Nonlinear Problems
    Chapter 7: Selected Applications
    Chapter 8: Algebraic Multigrid (AMG)
    Chapter 9: Multilevel Adaptive Methods
    Chapter 10: Finite Elements
    Bibliography
    Index

July 2000 / xii + 193 pages / Softcover / ISBN 0-89871-462-1
List Price $39.00 / SIAM Member Price $27.30 /  Order Code OT72

For more information, contact siam@siam.org or visit their website at
http://www.siam.org.

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

Date: Mon, 24 Jul 2000 15:37:48 +0200
From: Kees Venner 
Subject: Book on Multilevel Methods in Lubrication

I have worked (and am still working) with Achi Brandt and Ton Lubrecht on
multigrid solvers for integral equations and integro-differential problems.
In particular we have succeeded to develop fully efficient solvers for what is
called ``elastohydrodynamic lubrication'' problems.  This work was done over
the past 15 years.  We have now written a book describing the development and
relevant issues.  The book has the title ``Multilevel Methods in Lubrication''
and is published by Elsevier.  The book contains a detailed step by step
description towards a solver for the full problem, on its way passing a number
of problems that are of interest to a much wider community than only people in
lubrication.  In particular the techniques for integral equations, and fast
summation that appear are of interest to the multigrid community in general.
The book is aimed at students in technical sciences.  I don't know if new
books dealing with multigrid issues are normally mentioned on the MGNet site,
but if so then I would appreciate it if this could be done.  If you need more
details please let me know,

Kind regards, 
Kees Venner

C.H. Venner
University of Twente
Faculty of Mechanical Engineering
P.O. Box 217   7500 AE Enschede 
THE NETHERLANDS

                             * * * * * * * * * *

title:
    Multilevel Methods in Lubrication

authors:
    C.H. Venner,
       University of Twente, Department of Mechanical Engineering,
       Enschede, The Netherlands
    A.A. Lubrecht
       INSA de Lyon, Laboratoire de Mecanique des Contacts,
       Villeurbanne, France,

publisher:
    Elsevier

Series: Tribology Series Volume 37,

ISBN: 0-444-50503-2

The book is hard bound, 400 pages, and its price is 170 US$.  Attached to this
mail is a postscript file giving the title, authors, table of contents, and
the foreword of the book.  A description of the book, table of contents, price
and ordering information is also given on the web-page of Elsevier:

    http://www.elsevier.nl/inca/publications/store/6/2/1/2/1/4/

Contents

    Introduction
        Justification
        History
        Description of the EHL Problem
        Simpliication
        Model Problems
        Conclusion
        Advanced Topics
    Numerical Methods: Introduction
        Model Problems
        Discretization
        Systems of Equations
        Direct Solver
        Iterative Solver
        Relaxation
        Performance
        Local Mode Analysis
        Conclusion
        Advanced Topics
    Multigrid
        General Principle
        Correction Scheme
        Intergrid Transfers
        Coarse Grid Operator LH Coarse Grid Correction Cycle
        Cycle Performance
        Full MultiGrid
        Full Approxination Scheme
        1d Results
        2d Results
        Conclusion
        Advanced Techniques
    Hydrodynamic Lubrication
        Equations
        Discrete Equations
        Relaxation
        Caviation and Complementarity
        Coarse Grid Correction
        Full MultiGrid
        Accuracy
        Other L/R Ratios: Bearing Design
        Conclusion
        Advanced Topics 
        Dry Contact
    Equations
        Discrete Equations
        Relaxation
        Coarse Grid Correction
        Cycle Performance
        Full MultiGrid
        Multilevel Multi-Integration
        Incorporating MLMI into the FMG Solver
        Conclusion
        Advanced Topics
    Elastohydrodynamic Lubrication
        Introduction
        Equations
        Dimensionless Equations
        Dimensionless Parameters
        Discrete Equations
        Model Problems
        Relaxation of the EHL Problem
        Coarse Grid Correction Cycle
        Full MultiGrid
        Design Graphs
        Conclusion
        Advanced Topics

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

Date: Tue, 1 Aug 2000 10:50:04 -0400 (EDT)
From: Jun Zhang 
Subject: Half Injection and Full weighting in RBGS Smoothing

Solving Poisson equation on a square domain using red-black Gauss-Seidel
(RBGS) smoother in a standard multigrid method is always fascinating.  It
offers good parallelism, improved convergence rate, simpler grid transfer
requirement.  Most of the good properties of RBGS are not found in other type
of iterative methods.  For example, we usually expect to see a deteriorated
convergence rate when using RBGS ordering in stand along implementation or in
preconditioning techniques.

It is intuitively correct that, without considering the implementation cost,
the full weighting operator is always more accurate than the half injection
operator, in RBGS.  A few years ago, through numerical experiments, I observed
that this is indeed true only for V(1,1) cycle.  If I used more than one
relaxations on each level, say with V(2,2) cycle, then RBGS with the half
injection operator converges faster than RBGS with the full weighting
operator.  Here for convergence, I meant the number of iterations, not the CPU
time.  Of course, in this case, the former is faster too.  This observation
has been up and down in my mind for several years and I have not been able to
figure out an explanation.

I would appreciate it very much if someone has an answer to this question, to
send me an e-mail note.

Jun Zhang

**********************************************************************
* Jun Zhang                      * E-mail: jzhang@cs.uky.edu         *
* Department of Computer Science * URL:http://www.cs.uky.edu/~jzhang *
* University of Kentucky         * Tel:(859)257-3892                 *
* 773 Anderson Hall              * Fax:(859)323-1971                 *
* Lexington, Kentucky 40506-0046, USA                                *
**********************************************************************

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

Date: Wed, 12 Jul 2000 11:12:14 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Commentary

A number of presentations have been put into the virtual proceedings for the
Strobl (Austria) Workshop on Algebraic Multigrid Methods.  Of the 13 talks,
only two speakers have not contributed yet.  I am putting the titles and
abstracts in this issue and the next.  During that time, maybe the other two
speakers will make contributions (most of W-J is in this issue, H-A is in the
next).

All of the presentations are in http://www.mgnet.org/mgnet-amg2000-strobl.html,
however.  So you can look at them all now if you wish.  All of the titles were
listed in the last newsletter.

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

Date: Wed, 12 Jul 2000 11:12:11 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Wagner

                 On the Algebraic Construction of Multilevel
                              Transfer Operators

                               Christian Wagner

      IWR, Universitšt Heidelberg, INF 368, D-69120 Heidelberg, Germany
                phone: ++49-6221-548866, fax: ++49-6221-548860
                email: christian.wagner@iwr.uni-heidelberg.de

The standard way to construct coarse grids for algebraic multilevel methods is
a heuristic labeling of the nodes as C- and F-nodes.  While the F-nodes are
eliminated, the C-nodes built the coarse grid.  After that, in a separate
step, prolongation and restriction operators are constructed.

The basic idea of our new approach is to determine for each node those pairs
of nodes which allow an optimal interpolation of the considered node.  These
pairs of neighbor nodes (in some cases only one node) are called parent nodes.
A theoretical analysis shows that the problem of finding these parent nodes
for the node i can be reduced to a minimization problem of the form

                              minimize ||Y z||

where Y is a sort of a smoothing operator and z is allowed to have aside from
z_i = -1 only two non-zero entries.  Additionally, a filter condition (z,t)=0
with a given test vector t can be imposed.  The minimization problem can be
solved locally and is therefore relatively cheap.  These non-zero entries will
be the coefficients in the prolongation/restriction operators and the
corresponding nodes are the parent nodes.

After the possible pairs of parent node have been determined, the nodes are
labeled as C- and F-nodes such that each F-node can be interpolated using
these pairs of parent nodes and the already computed coefficients.
Additionally, a simple heuristic algorithm tries to minimize the number of
C-nodes and the number of edges in the coarse grid graph.

The construction scheme has been generalized to systems of partial
differential equations using a point-block approach.  The multilevel algorithm
has been parallelized and shows (almost) mesh size independent convergence for
standard model problems.  Realistic numerical experiments confirm the
efficiency of the presented algorithm.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

Date: Wed, 12 Jul 2000 11:12:10 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Stueben

          Some studies of the AMG performance in critical situations

                                Klaus Stueben

                                   Abstract

Algebraic multigrid has shown to be very efficient and robust for the solution
of various types of linear algebraic systems of equations, in particular those
arising from the discretization of scalar partial differential equations.
Major research is focusing on the extension of AMG to systems of partial
differential equations, for which a robustness and efficiency comparable to
that of the scalar case has not yet been reached.  But even for certain scalar
problems, the performance of AMG may substantially deteriorate.  We will
discuss several critical situations and possible remedies for some particular
scalar and systems problems.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

Date: Wed, 12 Jul 2000 11:12:09 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Reitzinger

             Algebraic Multigrid for 3D Magnetic Field Problems 1

                     Stefan Reitzinger - Joachim Schoeberl

                                   Abstract

In this talk we present a new algebraic multigrid method for the efficient
solution of the linear system arising from a finite element discretization of
variational equations in H_0(rot,Omega).  The finite element discretization is
done by Nedelec-elements (Whitney-1-forms or further referenced to as edge
elements).

An appropriate coarsening technique is presented in order to construct
suitable coarse spaces and according grid transfer operators.  The
prolongation operator is designed such that coarse grid kernel functions of
the rot-operator are mapped to fine grid kernel functions.  Furthermore,
coarse grid rot-free functions are discrete gradients.

The smoothers by Hiptmair and Arnold/Falk/Winther for H_0(rot,Omega)
variational problems can be used directly in the algebraic framework.

Collecting the ingredients (coarsening strategy, grid transfer operators,
smoother) we end up with an algebraic multigrid method for the considered
problem class.  Numerical studies are presented in order to show the
efficiency of the proposed technique.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

Date: Wed, 12 Jul 2000 11:12:08 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Pasciak

    Iterative techniques for mixed discretizations of Maxwells equations.

                              Joseph E. Pasciak

                                   Abstract

Maxwell equations in lossless media leads to a second order differential
equation for the electric field that is not elliptic, and is indefinite.  This
is a variational system involving an indefinite bilinear form in H(curl).  The
Galerkin discretization based on Nedelec spaces has been show to provide
accurate approximate solutions.  In this talk, the issue of preconditioning
the indefinite matrix arising from this method will be discussed.
Specifically, the overlapping Schwarz method will be shown to give rise to an
iterative scheme converging at a rate which independent of the the mesh size.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

Date: Wed, 12 Jul 2000 11:12:07 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Kraus

                 An Optimal Order Algebraic Multilevel Method

                                 J. K. Kraus

                                   Abstract

We consider preconditioners for large sparse matrices arising from
discretization of partial differential equations (PDEs) of predominant
elliptic type.  The author proposes a purely algebraic multilevel method based
on approximate cyclic reduction.  Within an incomplete LU decomposition
process spanning trees of matrix graphs are constructed that rest on a local
optimization principle.  A red-black coloring of these subgraphs yields the
partitioning of the unknowns (into fine- and coarse-grid variables) and is
also utilized to determine appropriate approximations of the Schur complements
(the coarse-grid operators) on different levels.

This idea is combined with algebraic multilevel iterations (AMLI) of V- and
W-cycle type.  The resulting method is robust with respect to anisotropy and
discontinuities in the coefficients of the PDEs.  It can be used with two- and
three-dimensional discretizations as well as with unstructured grids and is
also applicable to a class of nonselfadjoint boundary value problems.
Moreover, performing special W-cycles the resulting algorithm is shown to be
of optimal order of computational complexity under reasonable assumptions.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

Date: Wed, 12 Jul 2000 11:12:06 -0400
From: Craig Douglas 
Subject: AMG Presentation at Strobl - Jones

            Algebraic Multigrid for Finite Element Problems (AMGe)

                                 Jim E. Jones

                                   Abstract

We present an algebraic multigrid (AMG) method for finite element applications
which exploits information about the fine-grid elements.  In selecting the
coarse grid, we compare two approaches:  point-wise coarsening and element
agglomeration.  In both approaches, the interpolation operator satisfies a
local energy minimization principle.  Results show that the coarsening
approach can have a large impact on the convergence and complexity of the
overall method.

    Editor's Note: See http://www.mgnet.org/mgnet-amg2000-strobl.html
    -------------  for the hyperlinks.

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

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