Send mail to: mgnet@cs.yale.edu for the digests or bakeoff
mgnet-requests@cs.yale.edu for comments or help
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@cs.yale.edu)
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
IMMB'98
-------------------------------------------------------
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
carvalho@cerfacs.fr
Abstract
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/thesis.ps.gz
-------------
-------------------------------------------------------
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 http://www.mgnet.org/mgnet-tuts.html does not exist.
Cheers
Gundolf
Editor's Note: Does anyone have a copy? If so, please contact me.
-------------
-------------------------------------------------------
Date: Thu, 27 Nov 97 17:11:56 +0100
From: ghaase@tell.numa.uni-linz.ac.at (Dr. Gundolf Haase)
Subject: Papers at Johannes Kepler University, Linz, Austria
For some reports of interest see http://www.numa.uni-linz.ac.at
--> Publications --> Technical Reports
--> tr97-2.ps.gz
--> tr97-3.ps.gz
--> Publications --> Institute Reports
--> jkuma510.ps.gz
--> jkuma513.ps.gz
--> jkuma524.ps.gz
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
Abstract
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
Abstract
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
55(2):123-136.
[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
23(3).
[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
2:173-193.
[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
INSTITUT FUR MATHEMATIK
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
Abstract
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
Abstract
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
INSTITUT FUR MATHEMATIK
A-4040 LINZ, ALTENBERGERSTRASSE 69, AUSTRIA
Institutsbericht Nr. 524 June 1997
Abstract
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
Abstract
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
Abstract
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).
Topics
- 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
E-mail: mg10@iam.uni-bonn.de
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:
http://wwwwissrech.iam.uni-bonn.de/mg10
-------------------------------------------------------
Date: Wed, 26 Nov 1997 11:07:24 +0100 (MET)
From: "Alexander V. Padiy"
Subject: IMMB'98
FIRST ANNOUNCEMENT
Conference on
Iterative solution methods for the elasticity
equations as arising in mechanics and biomechanics
IMMB'98
University of Nijmegen, The Netherlands
September 28-30, 1998
SCOPE:
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.
THE PRIMARY TOPICS OF THE MEETING ARE:
- 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
INVITED SPEAKERS:
It is planned to invite several of the most active researchers in
the field. See further announcements for more details.
LANGUAGE AND PROCEEDINGS:
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 immb98@sci.kun.nl.
LaTeX2e format is preferred.
DEADLINES:
Deadline for submission of the extended abstracts : April 15, 1998
Referee reports and notification of acceptance : May 15, 1998
REGISTRATION FEES:
Early registration (before May 15, 1998) : 225 NLG
Late registration (after May 15, 1998) : 350 NLG
FOR FURTHER INFORMATION PLEASE CONTACT:
O. Axelsson or J. Padiy
University of Nijmegen
Department of Mathematics
Toernooiveld 1
NL-6525 ED Nijmegen
E-mail: immb98@sci.kun.nl
Fax : +31 (0)24 3652140
------------------------------
End of MGNet Digest
**************************