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 7, Number 11 (approximately November 30, 1997)

Today's topics:

     Thesis by Carvalho
     Marcus Speh's Multigrid Database
     Papers at Johannes Kepler University, Linz, Austria
     10th GAMM-Workshop on Multigrid Methods


Date: Sat, 08 Nov 1997 17:56:54 +0100
From: "Luiz M. Carvalho/" 
Subject: Thesis by Carvalho

                  Preconditioned Schur complement methods in
                       distributed memory environments

                               Luiz M. Carvalho

                          CERFACS, Toulouse, France


The use of domain decomposition methods in distributed memory parallel
environments for solving elliptic partial differential equations with high
discontinuity and high anisotropy is the main motivation for this work.  In
this respect, we propose local algebraic preconditioners for the Schur
complement method.  We show that these preconditioners are computationally and
numerically attractive when used in combination with a probing technique.

We propose and experiment with several coarse space components that are
combined with the local preconditioners.

We describe how these preconditioners are efficiently implemented on parallel
distributed memory computers using message passing or the virtual shared
memory paradigm in combination with efficient linear algebra kernels.  Though
the algebraic additive Schwarz (AAS) local preconditioner requires
communications between neighbouring subdomains and a few more floating-point
operations, the cost of one iteration of the preconditioned conjugate gradient
method (PCG) when using AAS or block Jacobi is almost the same.  Moreover, the
number of iterations of the PCG with AAS is reduced by 40% for highly
anisotropic problems.

We experiment with the new preconditioners on the linear systems that arise
from a device simulation code that we have parallelised.  Although the
preconditioners are not optimal, as their convergence depends on both H and
H/h, the experiments show that Schur complement domain decomposition methods,
using those preconditioners, solve efficiently the proposed device problems on
parallel distributed computers.

    Editor's Note: in mgnet/papers/Carvalho/


Date: Thu, 27 Nov 1997 07:22:47 +0100
From: "Dr. Gundolf Haase" 
Subject: Marcus Speh's Multigrid Database

it is a hard work to update all links on a web-page. 
I found that the link to "Marcus Speh's Multigrid Database" 
on does not exist. 


    Editor's Note: Does anyone have a copy?  If so, please contact me.


Date: Thu, 27 Nov 97 17:11:56 +0100
From: (Dr. Gundolf Haase)
Subject: Papers at Johannes Kepler University, Linz, Austria

For some reports of interest see

        --> Publications --> Technical Reports

        --> Publications --> Institute Reports

    Editor's Note: After some clarifications, the following is what you will
    -------------  find there.  I have pointers in mgnet-paper.html as well.

                              * * * * * * * * *

Hierarchical Extension Operators plus Smoothing
in Domain Decomposition Preconditioners

G. Haase
Applied Numerical Mathematics:23(3), May1997, pp. 327-346

The paper presents a cheap technique for the approximation of the harmonic
extension from the boundary into the interior of a domain with respect to a
given differential operator.  The new extension operator is based on the
hierarchical splitting of the given f.e. space together with smoothing sweeps
and an exact discrete harmonic extension on the lowest level and will be used
as a component in a domain decomposition (DD) preconditioner.  In combination
with an additional algorithmical improvement of this DD-preconditioner
solution times faster then the previously studied were achieved for the
preconditioned parallelized cg-method.  The analysis of the new extension
operator gives the result that in the 2D-case O(ln(ln(h^{-1}))) smoothing
sweeps per level are sufficient to achieve an h-independent behavior of the
preconditioned system provided that there exists a spectrally equivalent
preconditioner for the modified Schur complement with spectral equivalence
constants independent of h.

Keywords:  Boundary value problems, Finite element method, Domain
decomposition, Preconditioning, Parallel iterative solvers.

                              * * * * * * * * *

Multilevel Extension Techniques in Domain Decomposition Preconditioners

Gundolf Haase


One component in Additive Schwarz Method (ASM) Domain Decomposition (DD)
preconditioners [BPS89, SBG96] using inexact subdomain solvers [Boe89, HLM91]
consists in an operator extending the boundary data into the interior of each
subdomain, i.e., a homogeneous extension with respect to the differential
operator given in that subdomain.  This paper is concerned with the
construction of cheap extension operators using multilevel nodal bases [Yse86,
Xu89, BPX90, Osw94] from an implementation viewpoint.  Additional smoothing
sweeps in the extension operators further improve the condition number of the
preconditioned system.  The paper summarizes and improves results given in
[HLMN94, Nep95, Haa97].

References in Abstract

[Boe89] Boergers M. (1989) The Neumann-Dirichlet domain decomposition method
with inexact solvers on the subdomains.  Numerische Mathematik 

[BPS89] Bramble J., Pasciak J., and Schatz A. (1986, 1987, 1988, 1989) The
construction of preconditioners for elliptic problems by substructuring I-IV.
Mathematics of Computation 47:103-134, 49:1-16, 51:415-430, 53:1-24.

[BPX90] Bramble J., Pasciak J., and Xu J. (1990) Parallel multilevel
preconditioners.  Mathematics of Computation 55(191):1-22.

[Haa97] Haase G. (May 1997) Hierarchical extension operators plus smoothing in
domain decomposition preconditioners.  Applied Numerical Mathematics 

[HLM91] Haase G., Langer U., and Meyer A. (1991) The approximate Dirichlet
domain decompositionmethod.  Part I:  An algebraic approach.  Part II:
Applications to 2nd-order elliptic boundary value problems.  Computing
47:137-151 (Part I), 47:153-167 (Part II).

[HLMN94] Haase G., Langer U., Meyer A., and Nepomnyaschikh S.(1994)
Hierarchical extension operators and local multigrid methods in domain
decomposition preconditioners.  East-West Journal of Numerical Mathematics

[Nep95] Nepomnyaschikh S. (1995) Optimal multilevel extension operators.
Report 95-3, TU Chemnitz.

[Osw94] Oswald P. (1994) Multilevel Finite Element Approximation.  Teubner.

[SBG96] Smith B., Bjorstad P., and Gropp W. (1996) Domain Decomposition:
parallel methods for elliptic partial differential equations.  Cambridge
University Press.

[Xu89] Xu J. (1989) Theory of multilevel methods.  Technical Report AM48,
Department of Mathematics, Penn State University.

[Yse86] Yserentant H. (1986) On the multi-level splitting of finite element
spaces.  Numer. Math. 49(4):379-412.

                              * * * * * * * * *

An Incomplete Factorization Preconditioner
Based on a Non-Overlapping
Domain Decomposition Data Distribution

Gundolf Haase

Johannes Kepler University
Institut fur Mathematik 
A-4040 Linz, Altenbergerstrasse 69, Austria                     

A-4040 LINZ, ALTENBERGERSTRASSE 69, AUSTRIA                  
Institutsbericht Nr. 510 Dezember 1996

An Incomplete Factorization Preconditioner
Based on a Non-Overlapping
Domain Decomposition Data Distribution

December 10, 1996


The paper analyzes various parallel matrix-vector multiplications with
different matrix and vector types resulting from a non-overlapping domain
decomposition.  Under certain requirements to the f.e. mesh all given matrix
and vector types can be used in the multiplication.  The general framework
is applied to the investigation of the preconditioning step in cg-like
methods.  Not only the well-known domain decomposition preconditioners fit
into the concept but also parallelized global incomplete factorizations
are feasible.  Additionally, those global incomplete factorizationscan can be
used as smoothers in global multilevel methods.  Numerical results on a SPMD
parallel machine are presented.

Keywords :  Parallel iterative solvers, Incomplete Factorization,
Preconditioning, Domain decomposition, Finite element method.

                              * * * * * * * * *

Algebraic Multi-grid for Discrete Elliptic
Second-Order Problems

Ferdinand Kickinger

Institute for Mathematics, Johannes Kepler University Linz, Austria


This paper is devoted to the construction of Algebraic Multi-Grid (AMG)
methods, which are especially suited for the solution of large sparse systems
of algebraic equations arising from the finite element discretization of
second-order elliptic boundary value problems on unstructured, fine meshes in
two or three dimensions.  The only information needed is recovered from the
stiffness matrix.  We present two types of coarsening algorithms based on the
graph of the stiffness matrix.  In some special cases of nested mesh
refinement, we observe, that some geometrical version of the multi-grid method
turns out to be a special case of our AMG algorithms.  Finally, we apply our
algorithms on two and three dimensional heat conduction problems in domains
with complicated geometry (e.g., micro-scales), as well as to plane strain
elasticity problems with jumping coefflcients.

                              * * * * * * * * *

Explicit Extension Operators on Hierarchical Grids

Gundolf Haase

Johannes Kepler University
Institut fur Mathematik 
A-4040 Linz, Altenbergerstrasse 69, Austria                     

Sergej V. Nepomnyaschikh

Computing Center
Siberian Branchof Russian Academy of Sciences
Novosibirsk, 630090, Russia 

A-4040 LINZ, ALTENBERGERSTRASSE 69, AUSTRIA                  
Institutsbericht Nr. 524 June 1997


Extension operators extend functions defined on the boundary of a domain into
its interior.  This paper presents explicit extension operators by means of
multilevel decompositions on hierarchical grids.  It is shown that the
norm-preserving property of these operators holds for the 2D as well for the
3D case with constants independent on discretization and domain size.  These
constants can be further improved by an additional iteration scheme
applied to the extension operator.  Some implementation of these techniques is
presented for a domain decomposition preconditioner and numerical experiments
are given.

Keywords :  Boundary value problems, trace theory, multilevel methods, domain
decomposition, preconditioning, finite ele- ment method.

                              * * * * * * * * *

Robust MultigridPreconditioning for
Parameter-Dependent Problems I:
The Stokes-type Case

Joachim Schoberl

Johannes Kepler University
Institut fur Mathematik 
A-4040 Linz, Altenbergerstrasse 69, Austria                     


Parameter dependent problems can be discretized by selective reduced
integration methods to achieve parameter independent discretization errors.
The convergence rate of standard multigrid solvers applied to the primal
linear system deteriorates, if the parameter becomes small.  In this paper, we
construct multigrid components leading to parameter independentrates.  We need
a robust base iteration as smoother and uniformly continuous grid transfer
operations.  The suggested multigrid preconditioner is applied to problems
from linear elasticity.

                              * * * * * * * * *

Numerical Estimates of Inequalities in H1/2

Ferdinand Kickinger, Sergei V. Nepomnyaschikh,
Ralf U. Pfau, and Joachim Schoberl

August 28, 1997


The Sobolev norm H1/2(Gamma) plays a key role in domain
decomposition (DD) techniques.  For the efficiency of DD-preconditioners the
quantitative values of several constants is important.

The goal of this paper is the numerical investigation of the constants in
explicit extensions H1/2(Gamma)->H1(Omega) for the two
and three dimensional case, the discrete imbedding of H1/2(Gamma)
in Loo(Gamma) and of the norm estimates between
H1/2(Gamma) and Hoo1/2(Gamma).


Date: Wed, 26 Nov 1997 18:39:24 +0100
From: Gerhard Zumbusch 
Subject: 10th GAMM-Workshop on Multigrid Methods

                   FIRST ANNOUNCEMENT

              10th Anniversary International
          GAMM - Workshop on Multigrid Methods
          October 5 - 8, 1998 at Bonn (Germany).

- Theory and application of multigrid and multilevel methods
- Implementational issues
- Aspects of parallelization
- Applications in natural sciences and engineering

The organizing and programme committees are pleased to invite you to the
10th Anniversary International GAMM - Workshop on "Multigrid Methods".

The workshop will be held at the University Club of the University Bonn in
downtown Bonn. The aim of the workshop is to bring together again
scientists whose common interest is the theory and the application of
multigrid and related methods. The four-day programme will consist of
invited lectures, contributed papers and poster sessions.

Organized by the Department for Applied Mathematics, University Bonn
In Cooperation with the
- GAMM--Committee "Discretization Methods in Solid Mechanics"
- GAMM--Committee "Efficient Numerical Methods for PDEs"
- SFB 256 "Nichtlineare Partielle Differentialgleichungen"

Programme Committee
  Dietrich Braess (Bochum, Germany)
  Michael Griebel (Bonn, Germany)
  Wolfgang Hackbusch (Kiel, Germany)
  Ulrich Langer (Linz, Austria)

Local Organizing Committee
  Michael Griebel, Frank Kiefer, Gerhard Zumbusch

Conference Fees: With early registration: 80 DM, later: 100 DM
  We will provide limited low budget accommodation possibilities.

Deadlines and Important Dates:
  returning the early registration form February 15, 1998
  submitting the abstract May 15, 1998

for further information:


Date: Wed, 26 Nov 1997 11:07:24 +0100 (MET)
From: "Alexander V. Padiy" 
Subject: IMMB'98


Conference on
Iterative solution methods for the elasticity
equations as arising in mechanics and biomechanics 
University of Nijmegen, The Netherlands
September 28-30, 1998

 Recently there has been much progress reported on iterative solution
 methods for the solution of the algebraic systems which arise in finite
 element methods in structural engineering, geomechanics and biomechanics.
 The purpose of the conference is to report on recent progress and to enable 
 people from both the theoretical side and the practical, application side
 to meet and exchange their views on the topic.

 - Preconditioned conjugate gradient methods
 - Incomplete factorization methods, ordering strategies
 - Inner-outer iteration methods
 - Subspace iteration methods
 - Aggregation techniques
 - Superelement-by-element preconditioners
 - Algebraic multilevel methods
 - Multilevel domain decomposition methods
 - Locking phenomena
    - nearly incompressible materials
    - thin structures, limit cases (membrane state, bending state)
 - Conforming and non-conforming methods
 - Mixed variable methods
 - Reduced integration methods
 - Iteration methods for hybrid problems
 - Nonlinear materials and elasto-plastic problems
    - Incremental approaches
    - Newton-type methods
 - Finite element software packages, implementation aspects
 - Parallelization aspects 

 It is planned to invite several of the most active researchers in
 the field. See further announcements for more details.

 The working language will be English.
 The proceedings will contain the extended abstracts (up to 4 pages).
 The extended abstracts have to be submitted to
 LaTeX2e format is preferred.

 Deadline for submission of the extended abstracts : April 15, 1998
 Referee reports and notification of acceptance    : May   15, 1998

 Early registration (before May 15, 1998)          : 225 NLG
 Late  registration (after  May 15, 1998)          : 350 NLG

 O. Axelsson or J. Padiy
 University of Nijmegen
 Department of Mathematics
 Toernooiveld 1
 NL-6525 ED Nijmegen

 Fax   : +31 (0)24 3652140


End of MGNet Digest