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://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 9, Number 1 (approximately January 31, 1999) Today's topics: Original Site Online Again and New Web Design Poisson-solver in Fortran with MPI Introduction to Algebraic Multigrid (2 messages) 3 recent papers from the FEAST project Bonn Paper by Blaheta Bonn Paper by John and Tobiska Bonn Paper by Weiss, Kowarschik, Ruede, and Karl Bonn Paper by Iliev, Vassileva, and Drikakis Bonn Paper by Douglas, Hu, Ruede, and Bittencourt EMG '99 Call for papers International Workshop on Computational Physics in Beijing MAFELAP 1999 CALL FOR PAPERS ------------------------------------------------------- Date: Sun, 31 Jan 1999 11:23:22 +0100 From: Craig C. Douglas Subject: Original Site Online Again and New Web Design The web site http://casper.cs.yale.edu/mgnet/www/mgnet.html once again works. I put this back up in part due to the large number of broken hyperlinks that really ought to be changed to http://www.mgnet.org. Casper is not a high end (for its era) server anymore, but an ancient workstation. You will get better responses from the other sites, though Yale does have good network bandwidth. In addition, anyone visiting the web pages will note that they have all been redone. This has been a slow task that I have been working on since last June, primarily while on airplanes. An effort has been made to make the pages load faster than the old ones. ------------------------------------------------------- Date: Thu, 21 Jan 1999 15:24:29 +0100 From: "Dr. Rainer W. Hasse" Subject: Poisson-solver in Fortran with MPI Do you know where I can the Fortran source of a 2D Poisson solver for MPI? I need it for a PIC code. Editor's Note: There are several around including ones on MGNet in the ------------- codes' area (www.mgnet.org/mgnet-codes.html). See the Bunner and Douglas codes. In addition is MUDPACK, http://www.scd.ucar.edu/css/software/mudpack. Anyone else want to list their codes? ------------------------------------------------------- Date: Wed, 13 Jan 1999 20:04:20 +0100 From: "Dr. Christian Wagner" Subject: Introduction to Algebraic Multigrid The course notes Introduction to Algebraic Multigrid of an algebraic multigrid course for graduate and PhD students at the University of Heidelberg are now available. The discussed algebraic multigrid approaches are classified into several groups. One or two representatives of these groups are analyzed in detail, while the other members of these classes are briefly summarized. Theoretical and numerical results are presented. The selection of the algorithms is not assumed to be complete and does not induce any rating of the performance of algebraic multigrid methods. The course notes can be downloaded from my homepage at www.iwr.uni-heidelberg.de/iwr/techsim/chris Please let me know about any problem downloading the course notes. Christian Wagner * * * * * Date: Fri, 5 Feb 1999 19:25:44 +0000 From: "Dr. Christian Wagner" Subject: Introduction to Algebraic Multigrid I copied a new version (Version 1.1) of the course notes on algebraic multigrid to ftp.ccs.uky.edu:/mgnet/incoming/chris. The file is called amgV11.ps.gz. Dr. Christian Wagner IWR Technische Simulation office: 06221/548866 INF 368 fax: 06221/548860 D-69120 Heidelberg Christian.Wagner@iwr.uni-heidelberg.de Germany www.iwr.uni-heidelberg.de/iwr/techsim/chris Editor's Note: This can be referenced through either the tutorials web ------------- page www.mgnet.org/mgnet-tuts.html or the papers web page www.mgnet.org/mgnet-papers.html. It is located in www.mgnet.org/papers/Wagner/amgV11.ps.gz. ------------------------------------------------------- Date: Fri, 29 Jan 1999 15:47:07 +0100 (MET) From: ture@telemach.iwr.uni-heidelberg.de (Stefan Turek) Subject: 3 recent papers from the FEAST project Dear colleagues! ================ We have finished three (preliminary) papers which describe some recent developments in the FEAST software project which aims to combine sophisticated FEM techniques and powerful Multigrid approaches with high performance Numerical Linear Algebra tools. They can be downloaded from our Homepage at: http://gaia.iwr.uni-heidelberg.de/~ture/elch.html and we hope to get some interesting feed-back and further suggestions. 1) Proposal for `Sparse Banded BLAS' Techniques Summary: We present algorithmic and implementation details for Linear Algebra components in the context of `sparse banded' matrices as typical for FEM discretizations on generalized tensorproduct meshes. Based on appropriate reformulations of the matrix-vector applications in combination with blocking strategies, caching-in and internal vectorization facilities on the modern processors can be exploited. We give examples for the reachable high performance of several hundreds of MFLOP/s, depending on the actual hardware platform, which can be achieved for complete multigrid cycles with very sophisticated smoothers. 2) The `FEAST Indices' - Realistic evaluation of modern software components and processor technologies Summary: We examine the computational efficiency of Linear Algebra components in multigrid solvers for grid-oriented numerical simulations of PDE's. While the standard `sparse' Matrix-Vector techniques show significant losses of performance, especially on modern processors, the optimized `new' components have the potential to exploit today's high computing power. We explain the underlying concepts of the FEAST software which contains such individually adapted Numerical Linear Algebra components (`Sparse Banded BLAS') and correspondingly optimized complete multigrid solvers, all with respect to the actual hardware platform. Based on these algorithmic and computational studies, we present the `FEAST Indices' which are indicators for the true performance of many modern processors, depending on the underlying FEM space, the problem size and the implementation style. These Indices allow a new rating of the various hardware platforms with regard to different mathematical solution strategies, for academic and realistic numerical problems and ranging from `low cost' PC's up to supercomputers. 3) Trends in processor technology and their impact on Numerics for PDE's Summary: Processor technology is dramatically advancing and promises enormous improvements in `processing data' for the next decade. On the other hand, much lower advances in `moving data' are expected such that most available software for numerical simulations of Partial Differential Equations will be dominated by the cost for memory access. We demonstrate how `data locality' and `pipelining' can achieve a significant percentage of the huge computing power, and we explain how such techniques influence the corresponding numerical tools. Exemplarily, we describe new concepts for adaptive error control, multigrid/domain decomposition schemes and incompressible flow solvers and discuss their numerical and computational characteristics. Sincerely yours Stefan Turek + the FEAST Group Institute for Applied Mathematics University of Heidelberg INF 294 D-69120 Heidelberg Germany Phone: +49-6221-54-5714 Fax : +49-6221-54-5634 E-mail: ture@gaia.iwr.uni-heidelberg.de URL : http://gaia.iwr.uni-heidelberg.de/~ture ------------------------------------------------------- Date: Mon, 11 Jan 1999 10:03:01 -0500 (EST) From: Craig C. Douglas Subject: Bonn Paper by Blaheta Adaptive Composite Grid Methods for Problems of Plasticity Radim Blaheta The incremental FE method, which is a widely used procedure for the solution of problems of elasto-plasticity, is considered in this paper. An adaptive variant of this method is described as a tool for efficient computation of sufficiently accurate approximate solution. The main investigation is then devoted to the use of composite FE grids within the incremental FE methods. The attention is devoted mainly to implementation and convergence analysis of the Newton-FAC/BEPS iterative procedures for the solution of nonlinear systems arising within the load steps. Editor's Note: This can be found through www.mgnet.org/mgnet-parmgm98.html ------------- or mgnet/Conferences/ParMGM98/Papers/blaheta.ps.gz ------------------------------------------------------- Date: Wed, 20 Jan 1999 04:39:02 -0500 (EST) From: Craig C. Douglas Subject: Bonn Paper by John and Tobiska A Coupled Multigrid Method for Nonconforming Finite Element Discretizations of the Stokes Equation Volker John and Lutz Tobiska This paper investigates a multigrid method for the solution of the saddle point formulation of the discrete Stokes equation obtained with inf-sup stable nonconforming finite elements of lowest order. A smoother proposed by Braess and Sarazin (1997) is used and L2-projection as well as simple averaging are considered as prolongation. The W-cycle convergence in the L2-norm of the velocity with a rate independently of the level and linearly decreasing with increasing number of smoothing steps is proven. Numerical tests confirm the theoretically predicted results. Editor's Note: This can be found through www.mgnet.org/mgnet-parmgm98.html ------------- or mgnet/Conferences/ParMGM98/Papers/john.ps.gz ------------------------------------------------------- Date: Thu, 28 Jan 1999 06:47:03 -0500 (EST) From: Craig C. Douglas Subject: Bonn Paper by Weiss, Kowarschik, Ruede, and Karl Cache-Aware Multigrid Methods for Solving Poisson's Equation in Two Dimensions Christian Weiss, Markus Kowarschik, Ulrich Ruede, and Wolfgang Karl Conventional implementations of iterative numerical algorithms, especially multigrid methods, merely reach a disappointing small percentage of the theoretically available CPU performance when applied to representative large problems. One of the most important reasons for this phenomenon is that the need for data locality due to poor main memory latency and limited bandwidth is entirely neglected by many developers designing numerical software. Only when most of the data to be accessed during the computation are found in the system cache (or in one of the caches if the machine architecture comprises a cache hierarchy) fast program execution can be expected. Otherwise, i.e. in case of a significant rate of cache misses, the processor must stay idle until the necessary operands are fetched from main memory, whose cycle time is in general extremely large compared to the time needed to execute a floating point instruction. In this paper, we describe program transformation techniques developed to improve the cache performance of two-dimensional multigrid algorithms. Although we merely consider the solution of Poisson's equation on the unit square using structured grids, our techniques provide valuable hints towards the efficient treatment of more general problems. Key words. multigrid, cache memories, iterative methods, high performance computing, code optimization AMS subject classifications. 68-04, 65F10 Editor's Note: This can be found through www.mgnet.org/mgnet-parmgm98.html ------------- or mgnet/Conferences/ParMGM98/Papers/kowarschik.ps.gz ------------------------------------------------------- Date: Fri, 29 Jan 1999 11:56:04 -0500 (EST) From: Craig C. Douglas Subject: Bonn Paper by Iliev, Vassileva, and Drikakis Adaptive-Smoothing Multigrid Algorithm for Fluid Flow Computations O. P. Iliev, D. P. Vassileva, and D. Drikakis A computational approach for increasing the efficiency of multigrid solvers in computational fluid dynamics (CFD) problems is presented. An adaptive-smoothing multigrid algorithm (AS-MG) is developed in conjunction with a full-multigrid, full-approximation-storage (FMG-FAS) method and an incompressible three-dimensional Navier-Stokes solver. The AS-MG algorithm reduces the overall computational cost by performing smoothings in subsets of the computational grid. The latter are defined adaptively at each multigrid sweep according to a prescribed criterion. Three different adaptivity criteria are investigated in connection with the computation of external and internal flows. Several numerical experiments are presented in order to demonstrate the advantages of the new algorithm. Editor's Note: This can be found through www.mgnet.org/mgnet-parmgm98.html ------------- or mgnet/Conferences/ParMGM98/Papers/iliev.ps.gz. While only 13 pages long, this unpacks to be about 45 megabytes!!! ------------------------------------------------------- Date: Fri, 01 Feb 1999 08:44:05 -0500 (EST) From: Craig C. Douglas Subject: Bonn Paper by Douglas, Hu, Ruede, and Bittencourt Cache Based Multigrid on Unstructured Two Dimensional Grids Craig C. Douglas, Jonathan Hu, Ulrich Ruede, and Marco L. Bittencourt High speed cache memory is commonly used to address the disparity between the speed of a computer's central processing unit and the speed of a computer's main memory. It is advantageous to maximize the amount of time that data spends in cache. Tiling is a software technique which is often used to do just this. Tiling is not able, however, to handle dynamically changing data structures, such as those encountered in adaptively chosen, unstructured grids. We develop a variant of the Gauss-Seidel method for second order elliptic partial differential equations with variable coefficients. This variant keeps data in cache memory for much longer than non-cache implementations. As a result, our method is significantly faster than non-cache implementations. Examples from the structured grid case demonstrate the benefits of such a variant and provide motivation for the more difficult unstructured grid case. For this case, a publicly available load balancing package is used to decompose the grid into blocks of nodes which fit into cache. An O(n) algorithm is introduced that provides a one-time reordering of the nodes in each block. This new ordering permits significantly more Gauss-Seidel updates and residual calculation to be done in cache than in standard implementations. The cache aware Gauss-Seidel variant is incorporated into a multigrid code and tested by solving two dimensional linear elastic problems with multiple degrees of freedom per node. These experiments demonstrate cache hit rates and cache line reuse possible with a multigrid V cycle that incorporates such a cache aware method. Key words. multigrid, unstructured grids, cache, tiling, iterative methods, domain decomposition, partial differential equations, software. AMS subject classifications. 65M55, 65N55, 65F10, 65N30, 65F50, 65N50 Editor's Note: This can be found through www.mgnet.org/mgnet-parmgm98.html ------------- or mgnet/Conferences/ParMGM98/Papers/douglas.ps.gz ------------------------------------------------------- Date: Fri, 05 Feb 1999 12:33:38 +0100 From Erik.Dick@rug.ac.be Fri Feb 5 09:39 EST 1999 Subject: EMG '99 Call for papers Call For Papers Sixth European Multigrid Conference September 27-30, 1999 Universiteit Gent, Belgium The department of Flow, Heat and Combustion Mechanics of the University of Gent will host the sixth European Multigrid Conference. Conference themes concern all aspects of multigrid methods: theory and applications. The conference will be held in the main building of the Faculty of Applied Sciences of the university, located in the heart of the city of Gent. The conference fee will be 300 Euro, including admission to all sessions, lunches, coffee breaks, reception, conference dinner, excursion, book of abstracts and a copy of the proceedings published by Springer. Paper Submission Authors should submit an abstract of about 500 words, with supporting figures, to the symposium chairman. Submission by e-mail is allowed. The abstract should contain: 1) keywords to categorize the work; 2) name, address, phone, fax and e-mail of the author to whom correspondence should be directed. The deadline for submitting the abstract is April 19, 1999. Notification of acceptance will be given by June 15, 1999. A one-page abstract of accepted papers for inclusion in the book of abstracts will be due by September 10, 1999. Papers for inclusion in the proceedings should be given in camera-ready form to the conference desk during the conference. Publication of the proceedings is expected for March 2000. Symposium Chairman Prof. E. Dick Universiteit Gent Department of Flow, Heat and Combustion Mechanics Sint-Pietersnieuwstraat 41 9000 Gent, Belgium Fax +31-09-264 3586 Tel +31-09-264 3301 e-mail: erik.dick@rug.ac.be ------------------------------------------------------- Date: Fri, 22 Jan 1999 10:11:15 -0600 From: Zhangxin CHEN Subject: International Workshop on Computational Physics in Beijing First Announcement and Call for Papers International Workshop on Computational Physics: Fluid Flow and Transport in Porous Media Place: The International Center of Computational Physics, Beijing, China Date: August 2-6, 1999 Co-sponsored and supported by National Natural Science Foundation of China The Beijing Institute of Applied Physics and Computational Mathematics The Chinese State Key Basic Research Project The U.S. Army Research Office The Asian Office of Aerospace Research and Development The Office of Naval Research International Program Committee: Zhangxin Chen (Chairman), Southern Methodist University, USA Jim Douglas, Jr., Purdue University, USA Richard E. Ewing (Co-Chairman), Texas A&M University, USA Michele L. D. Gaudreault, Office of Aerospace Research & Development, USA Ian Gladwell, Southern Methodist University, USA Huan-Guan Ren, China National Petroleum Corp., China Long-Jun Shen, Beijing Institute of Applied Physics and Computational Mathematics, China Zhong-Ci Shi (Co-Chairman), Academy of Sciences, China Julian J. Wu, U.S. Army Research Office (ARO), USA Yi-Rang Yuan, Shandong University, China Invited Speakers (confirmed): Todd Arbogast, University of Texas at Austin, USA Zhangxin Chen, Southern Methodist University, USA Craig Douglas, University of Kentucky, USA Jim Douglas, Jr., Purdue University, USA Magne Espedal, University of Bergen, Norway Richard E. Ewing, Texas A&M University, USA Jerome Jaffre, INRIA-Rocquencourt, France Stephen L. Lyon, Mobil, USA Hou-De Han, Tsinghua University, China Kai-Tai Li, Xi'an Jaiotong University, China Guan Qin, Mobil, USA Thomas Russell, University of Colorado, USA Robert Sharpley, University of South Carolina, USA Long-Jun Shen, IAPCM, China Zhong-Ci Shi, Academy of Sciences, China Bing Wang, Institute of Atmospherical Physics, China Hong Wang, University of South Carolina, USA Mary F. Wheeler, University of Texas at Austin, USA Yi-Rang Yuan, Shandong University, China Guan-Quan Zhang, Academy of Sciences, China Local Organization Committee: Zhong-Zhi Bai, CAS, Beijing Long-Jun Shen, IAPCM, Beijing Xi-Jun Yu, IAPCM, Beijing Shi-Zhen Zhang, CAS, Beijing Workshop Themes: (1) Flow and Transport in Porous Media (2) Numerical Methods (3) Parallel Computation (4) Optimization (5) Surface Water and Ocean Modeling (6) Chemically Reactive Phenomena (7) Environmental Remediation (8) Atmospheric Modeling (9) Earthquake Modeling (10) Multiscale Phenomena (11) Media Characterization Workshop Format: The workshop will consist of 45-minute invited talks and 25-minute contributed presentations. The workshop language is English. Workshop Proceedings: Proceedings of presented and refereed papers will be published. Call for Papers: People wishing to present a paper in a field related to the workshop themes are invited to submit a one-page abstract by April 30, 1999 to Dr. Xi-Jun YU. Email: y_xijun@hotmail.com, fax: (86-10) 6205-7289, and mailing address: Lab of Computational Physics, Institute of Applied Physics and Computational Mathematics, PO Box 8009-26, Beijing 100088, P.R. China. ------------------------------------------------------- Date: Fri, 29 Jan 1999 15:53:33 +0000 (GMT) From: John R Whiteman Subject: MAFELAP 1999 CALL FOR PAPERS MAFELAP 1999 Tenth Conference on The Mathematics of Finite Elements and Applications Brunel University, Uxbridge, UK 22-25 June 1999 CALL FOR PAPERS The Tenth Conference on The Mathematics of Finite Elements and Applications will be held at Brunel University from 22-25 June, 1999. The aim will again be to bring together workers from different disciplines whose common interest is finite element methods, and to promote wider awareness throughout the finite element community of the latest developments in the field TOPICS * Theory and practice in finite elements * Finite volume methods * Engineering and scientific applications of FEM * Boundary element methods * Adaptivity * Singularities * Parallel and vector processing * CFD and structural mechanics * Flow in porous media INVITED SPEAKERS The 1999 Zienkiewicz Lecture will be given by Roland Glowinski, University of Houston Ulrich Langer, Linz University Roland Lewis, University of Wales, Swansea J Tinsley Oden, University of Texas at Austin Roger Owen, University of Wales, Swansea Rolf Rannacher, University of Heidelberg Christof Schwab, ETH Zuerich Endre Suli, University of Oxford Mary Wheeler, University of Texas at Austin John Whiteman, Brunel University Peter Wriggers, Technical University of Hannover Luiz Wrobel, Brunel University THE PROGRAMME, CALL FOR PAPERS AND SUBMISSION OF TITLES/ABSTRACTS In addition to the invited lectures, the programme will contain lectures in parallel sessions, sessions of poster papers, and mini-symposia. Following the preliminary announcement of MAFELAP 1999 a large number of persons have indicated that they wish to present papers or to organise mini-symposia at the conference. The topics proposed to date for these are given below. Anyone who has accepted an invitation to participate in a mini-symposium should send the title of his/her talk to the organiser of the mini-symposium as soon as possible. The abstract of the talk should be submitted to MAFELAP electronically by 31 March 1999 as per the instructions on the MAFELAP web site. Anyone who wishes to present either a lecture in a parallel session or a poster paper is asked to submit an abstract as soon as possible and, in any case not later than 26 February 1999. MINI-SYMPOSIA TOPICS TO DATE INCLUDE * Domain decomposition preconditioners * A posteriori error estimation and reliability of FE computations * Optimal and moving meshes * Anisotropic Mesh Adaptivity for Finite Element Methods * Boundary element methods for wave scattering problems * Computational modelling of forming processes * Adaptive methods for time dependent problems * Numerical treatment of singularities * Fluid structure interactions * Time Harmonic Maxwell problems * Compressible flow * Computational modelling of plasticity * Finite and infinite elements for exterior problems * Adaptivity and applications of domain decomposition methods * Applications of finite element analysis to composite materials and plates * Finite and boundary element methods for fluid-structure interaction problems * Finite elements in problems of biomechanics * Computational modelling of solids with evolving geometries and multiple fracturing * Adaptive methods for viscoelastic flow problems * Mathematical modelling in geomechanics and tunnelling * Problems of magnetism * Heirarchical modelling * Multi-field problems * Superconvergence and recovery for finite element methods * Numerical analysis of contact mechanics FURTHER DETAILS AND ENQUIRIES Further details are available from the MAFELAP 1999 web page: http://www.brunel.ac.uk/~icsrbicm/maflap99/home.html and also from The Secretary, MAFELAP 1999, BICOM, The Brunel Institute of Computational Mathematics, Brunel University, Uxbridge UB8 3PH, UK Tel: Int. (+44) 1895 203270 Fax: Int. (+44) 1895 203303 email mafelap@brunel.ac.uk ------------------------------ End of MGNet Digest **************************