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 McCormickSubject: 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 **************************