Send mail to: mgnet@cs.yale.edu for the digests mgnet-requests@cs.yale.edu for comments or help 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 **************************