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://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 2 (approximately February 28, 1999) Today's topics: Important Date Microsoft Word Documents EMG'99 home page Copper Mountain Preliminary Program Online PLTMG8.1 on MGNet MGCG Mathematical/Computational Techniques for Multilevel Adaptive Methods Paper on Global Hall Conductor in the Earth's Ionosphere Viscous Incompressible/Low-Mach-Number Flows on High Aspect Ratio Grids Paper on Stress Concentration Problems 4 Copper Mountain Papers Two prints from Jun Zhang Teigland Bibliography Update International Conference on Preconditioning Techniques ------------------------------------------------------- Date: Sun, 28 Feb 1999 11:23:22 +0500 From: Craig C. DouglasSubject: Important Date March 11 Hotel reservations for the Copper Mountain Conference on Multigrid Methods. See http://www.mgnet.org/mgnet-conferences.html for a link to the conference. ------------------------------------------------------- Date: Sun, 28 Feb 1999 15:42:55 +0500 From: Craig C. Douglas Subject: Microsoft Word Documents I am receiving more and more preprints or papers for virtual proceeding papers produced using Microsoft Word. Some I can look at on my laptop and some I cannot. There are several common themes that will make submission much quicker. If your document uses special fonts, it will probably not be renderable by the vast majority of MGNet readers. Also, one of the options in Word2000 is to save files in HTML format in a manner that is supposed to be lossless. The font problem still exists in this case. If you use a different separator than the default , (Windows), you might save the file once with the default separator. A quick fix is to submit either an Adobe PDF file as well or to use "print to file" using the Apple Laserwriter printer driver (the ancient printer, not a PostScript level 3 driver). The PDF file will be closer to what your document looks like under Word. ------------------------------------------------------- Date: Tue, 09 Feb 1999 09:36:17 +0100 From: Kris Riemslagh Subject: EMG'99 home page We forgot to include a reference to our home-page in the call for papers of the EMG 99. Please include the following link at your EMG99 page: http://allserv.rug.ac.be/~edick/emg/ Dr. ir. Kris Riemslagh Universiteit Gent Vakgroep Werktuigkunde en Warmtetechniek Dept. Mechanical and Thermal Engineering Sint Pietersnieuwstraat 41 B-9000 GENT, Belgie Tel: +32/9/264.33.13; Fax: +32/9/264.35.86 E-mail: Kris.Riemslagh@rug.ac.be ------------------------------------------------------- Date: Sun, 28 Feb 1999 11:25:21 +0500 From: Craig C. Douglas Subject: Copper Mountain Preliminary Program Online The Copper Mountain preliminary program (still tentative) is at http://amath-www.colorado.edu/appm/faculty/copper/1999/program.html ------------------------------------------------------- Date: Mon, 08 Feb 1999 10:26:20 -0800 From: "Randolph E. Bank" Subject: PLTMG8.1 on MGNet I would like to update pltmg8.0 with pltmg8.1. Functionally, this version is identical to pltmg8.0. A few bugs have been fixed, and the driver program routines have been reworked a bit. In particular, xgraph.c should be more compatible with default linux X-windows configurations. Randolph E. Bank Tel: (619) 534-4204 Department of Mathematics Fax: (619) 534-5273 University of California, San Diego Email: rbank@ucsd.edu La Jolla, CA 92093-0112 http://sdna3.ucsd.edu/~reb Editor's Note: See http://www.mgnet.org/mgnet-codes-pltmg.html ------------- ------------------------------------------------------- Date: Mon, 01 Mar 1999 12:20:48 -0500 From: "E. Bruce Pitman" Subject: MGCG I am looking for papers and any code that might be available, using multigrid as a preconditioner to a CG solver. Any pointers will be greatly appreciated. E. Bruce Pitman Professor Director of Graduate Studies Department of Mathematics 106 Diefendorf Hall State University of New York Buffalo, NY 14214-3093 (716)829-2144 voice (716)829-2299 fax pitman@galileo.math.buffalo.edu Center for Computational Research http://www.math.buffalo.edu/~pitman http://www.ccr.buffalo.edu ------------------------------------------------------- Date: Mon, 1 Mar 1999 12:41:14 From: Subject: Mathematical/Computational Techniques for Multilevel Adaptive Methods Je suis etudiant tchadien. Le tchad est un pays africain. Je prepare une these sur "mathematical and computational techniques for multilevel adaptive methods". Je voudrais avoir une documentation complete en anglais sur le sujet. Je veux aussi les travaux recents sur les multigrilles et les multiniveaux adaptative. mon adresse: Djibet M'bainguesse enseignant et chercheur faculte des sciences exactes et appliquees Universite du Tchad bp1027 N'djamena Tchad. ------------------------------------------------------- Date: Fri, 12 Feb 1999 10:43:34 +0700 From: "Valeri Denissenko" Subject: Paper on Global Hall Conductor in the Earth's Ionosphere Multigrid Method for a Global Hall Conductor in the Earth's Ionosphere Valeri V. Denissenko Institute of Computational Modelling Krasnoyarsk, 660036, Russia Abstract Since conductivity is an asymmetric tensor in the ionosphere the elliptical operators of the boundary value problems are not selfadjoint. To overcome difficulties that arise in numerical solution of problems with not selfadjoint operators it is proposed to replace the traditional statements with new ones in which the operators are symmetrical and positive definite. A narrow boundary strip in that the coefficients are huge in comparing with those in the interior of the domain is separated with a special boundary condition. The finite element equations are obtained as a conditions of a minimum of the energy functional with a special set of parameters to approximate the main boundary conditions. Positive definiteness of the matrix is proved. A multigrid method that is used to solve these equations and a numerical example are presented. Key words. gyrotropic transfer, Hall conductivity, symmetrization, elliptic equation, variational principle, finite elements, multigrid method AMS subject classifications. Primary 65N30, 35J50; Secondary 78A25 Editor's Note: See http://www.mgnet.org/mgnet-parmgm98.html or ------------- http://www.mgnet.org/Conferences/ParMGM98/Papers/denissenko.ps.gz ------------------------------------------------------- Date: Thu, 25 Feb 1999 14:56:23 +0100 From: Jan Vierendeels Subject: Viscous Incompressible/Low-Mach-Number Flows on High Aspect Ratio Grids A Multigrid Semi-Implicit Line Method for Viscous Incompressible and Low-Mach-Number Flows on High Aspect Ratio Grids Jan Vierendeels, Kris Riemslagh, and Erik Dick Department of Mechanical and Thermal Engineering Universiteit Gent, Belgium Abstract Discretization of viscous incompressible and viscous low-Mach-number flows often leads to a system of equations, which is very difficult to solve. There are two reasons. First, the use of high aspect ratio grids results in a very numerically anisotropic behaviour of the diffusive and acoustic terms and second, in low-Mach-number flow, the ratio of the convective and acoustic eigenvalues of the inviscid system becomes very high. We implemented an AUSM based discretization method, using an explicit third-order discretization for the convective part, a line-implicit central discretization for the acoustic part and for the diffusive part. The lines are chosen in the direction of the gridpoints with shortest connection. The preconditioned semi-implicit line method is used in multistage form because of the explicit third-order discretization of the convective part. Multigrid is used as acceleration technique. It is shown that the convergence is very good, independent of grid aspect ratio and Mach number. Editor's Note: See http://www.mgnet.org/mgnet-parmgm98.html or ------------- http://www.mgnet.org/Conferences/ParMGM98/Papers/vierendeels.ps.gz ------------------------------------------------------- Date: Mon, 1 Mar 1999 01:37:23 -0800 (PST) From: Alexander Trofimov Subject: Paper on Stress Concentration Problems Multigrid Methods for Stress Concentration Problems Alexander V. Trofimov Dnepropetrovsk State University, Ukraine Abstract Some aspects of the Multigrid Methods implementation to stress concentration problems are discussed. Convenient variational formulations for such problems are proposed. Computational aspects of Richardson's extrapolation methods implementation and nonlinear iterations are investigated. The efficiency of multigrid and some other widespread algorithms is compared. Warning: The correct drawing of mathematical symbols depends on the Windows tuning parameter "list separator." You have to choose Control Panel -> Regional Settings -> Numbers -> List separator It must be set to ";" (semicolon) Editor's Note: See http://www.mgnet.org/mgnet-parmgm98.html or ------------- http://www.mgnet.org/Conferences/ParMGM98/Papers/trofimov.doc ------------------------------------------------------- Date: Sun, 28 Feb 1999 16:18:20 +0500 From: Craig C. Douglas Subject: 4 Copper Mountain Papers The Application of the Multigrid Method in a Nonhydrostatic Atmospheric Model Shu-Hua Chen Department of Earth and Atmospheric Sciences Purdue University West Lafayette, IN 47907, USA Abstract A nonhydrostatic atmospheric model is developed. The use of the Semi-implicit scheme in this model has relaxed the constraint of exceedingly small time step, but it generates a huge sparse matrix (400,000 x 400,000) of the Elliptic Partial Differential Equations (EPDEs). This study attempts to apply the Multigrid method to solve these EPDEs and to address the performance and efflciency of the Multigrid method. Two experiments are examined. The model results are in good agreement with those in historical papers and the analytical solution. Furthermore, the Multigrid solver, mud3cr, applied in this model is very efflcient. These indicate the success of the Muitigrid method applied to nonhydrostatic atmospheric models. Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or ------------- http://www.mgnet.org/Conferences/CopperMtn99/Papers/chen.ps.gz * * * * * Cache Based Multigrid on Unstructured Grids Jonathan Hu Universityof Kentucky Departmentof Mathematics 715 Patterson Offlce Tower Lexington, KY 40506-0027, USA Abstract High speed cache memory is commonly used to address the disparity between the speed of a computer's central processing unitand the computer's main memory speed. 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 are encountered in adaptively chosen, unstructured grids. We develop a variant of the Gauss-Seidel method which 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 motiv ation for the more difflcult unstructured grid case. For this case, an O(n) algorithm is introduced that divides nodes into blocks whichf it into cache. This leads to a new ordering which allows significantly more Gauss-Seidel updates and residual calculation to be done in cache than in standard implementations. Numerical experiments demonstrate the speedups possible with the cache aware Gauss-Seidel method and with a multigrid V cycle using the cache aware method. Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or ------------- http://www.mgnet.org/Conferences/CopperMtn99/Papers/hu.ps.gz * * * * * A Multigrid Strategy for Accelerating Steady-State Computations of Waves Propagating with Curvature Dependent Speeds Jonathan Rochez Department of Applied Science University of California, Davis Davis, CA, USA Abstract A multigrid strategy is developed for accelerating the steady state computations of waves propagating with curvature dependent speeds. This will allow the rapid computation of a ``burn table.'' In a high explosive material, the creation of a burn table will allow the elimination of solving chemical reaction ODEs and feed in source terms to the reactive flow equations for solution of the system of ignition of the high explosive material. Standard iterative methods show a quick reduction of the residual followed by a slow final convergence to the solution at high iterations. Such systems are excellent choices for the use of multigrid methods to speed up convergence, even on a nonlinear system such as this. Numerical steady-state solutions to the eikonal equationon on a rectangular grid are conducted. Results are presented for a square grid in 2D and a cubic grid in 3D using a Runge-Kutta time iteration for the smoothing operator until steady-state is reached. Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or ------------- http://www.mgnet.org/Conferences/CopperMtn99/Papers/rochez.ps.gz * * * * * Fourier Analysis of GMRES(m) Preconditioned by Multigrid R. Wienands GMD Institute for Algorithms and Scientific Computing D-53754 St. Augustin, Germany Abstract This paper deals with convergence estimations of a preconditioned GMRES(m) method, where multigrid is used as the preconditioner. Fourier analysis is a well-known useful tool in the multigrid community for the prediction of two-grid convergence rates. This analysis is generalized to the situation where multigrid is a preconditioner. Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or ------------- http://www.mgnet.org/Conferences/CopperMtn99/Papers/wienands.ps.gz ------------------------------------------------------- Date: Sun, 28 Feb 1999 11:55:54 -0500 (EST) From: Jun Zhang Subject: Two prints from Jun Zhang A Grid Based Multilevel Incomplete LU Factorization Preconditioning Technique for General Sparse Matrices Jun Zhang Department of Computer Science, University of Kentucky 773 Anderson Hall, Lexington, KY 40506--0046, USA ABSTRACT We design a grid based multilevel incomplete LU preconditioner (GILUM) for solving general sparse matrices. This preconditioner combines a high accuracy ILU factorization with an algebraic multilevel recursive reduction. The GILUM preconditioner is a compliment to the domain based multilevel block ILUT preconditioner. A major difference between these two preconditioners is the way that the coarse level nodes are chosen. In this sense the approach of GILUM is analogous to that of algebraic multigrid method. However, the GILUM construction is completely different from the algebraic multigrid construction. A partial ILUT factorization is applied to the reordered matrix and the coarse level system is obtained implicitly. The incomplete factorization process is repeated with the coarse level systems recursively. The GILUM approach avoids some controversial issues in algebraic multigrid method such as how to construct the interlevel transfer operators and how to compute the coarse level operator. Numerical experiments are conducted to compare GILUM with other ILU preconditioners. * * * * * RILUM: A General Framework for Robust Multilevel Recursive Incomplete LU Preconditioning Techniques Jun Zhang Department of Computer Science, University of Kentucky 773 Anderson Hall, Lexington, KY 40506--0046, USA ABSTRACT We introduce a general framework for constructing multilevel recursive incomplete LU preconditioning techniques (RILUM) for solving general sparse matrices. This technique is based on a recursive two by two block incomplete LU factorization on the coefficient matrix. The coarse level system is constructed as an (approximate) Schur complement. A dynamic preconditioner is obtained by solving the Schur complement matrix approximately. The novelty of the proposed techniques is to solve the Schur complement matrix by a preconditioned Krylov subspace method. The very preconditioner for this secondary iteration is constructed by considering the Schur complement matrix as a general sparse matrix and by applying to it the block ILU factorization process that was applied to the original matrix. This recursive procedure continues for a few times and results in a multilevel preconditioner. Different implementation strategies are discussed. We conduct numerical experiments with two particular RILUM implementations to show the performance of the proposed techniques and to demonstrate grid independent convergence rates of RILUM for solving certain problems. Editor's Note: See http://www.cs.uky.edu/~jzhang ------------- ------------------------------------------------------- Date: Mon, 15 Feb 1999 16:05:21 +0100 From: Rune Teigland Subject: Teigland Bibliography Update Please find attached a listing of my contributions related to multigrid/domain decomposition. @phdthesis{ author = "Teigland, R.", title = "On Multilevel Methods for Numerical Reservoir Simulation, Report No. 92, October 1991, ISSN 0084-778x", school = "University of Bergen, Norway", year = "1991", } @inproceedings{ author = "Teigland R. and Fladmark G.E.", title = "Cell-centered Multilevel Methods in Reservoir Simulation", booktitle = "International Series of Numerical Mathematics", volume = "98", year = "1991", pages = "365-376", publisher = "Birkhauser Verlag, Basel." } @article{ author = "Ersland B.G. and Teigland R.", title = "Comparison of Two Cell-Centered Multigrid Schemes for Problems with Discontinuous Coefficients", journal = "Numer. Meth. for PDE", volume = "9", year = "1993", pages = "265-283", } @inproceedings{ author = "Teigland, R.", title = "An Additive {S}chwarz Procedure for Complex Flows", editor = "Paul A. Thibault and Denis M. Bergeron", booktitle = "Proc. Third Annual Conference of the CFD Society of Canada", year = 1995, pages = "145-152" } @inproceedings{ author = "Gjesdal T., Lossius M.E.H., Teigland R.", title = "Multigrid Solution of Incompressible Flow Using Pressure Correction Smoothers", editor = "Paul A. Thibault and Denis M. Bergeron", booktitle = "Proc. Third Annual Conference of the CFD Society of Canada", year = 1995, pages = "145-152" } @article{ author = "Teigland R.", title = "On some variational acceleration techniques and related methods for local refinement", journal = "Int. J. Numer. Meth. Fluids", volume = "28", year = "1998", pages = "945-960", } @inproceedings{ author = "Teigland, R.", title = "A Domain Decomposition Strategy for Simulation of Complex Industrial Fluid Flows", booktitle = "Proc. Ninth Int. Conf. on Domain Decomposition", editors = "P.E. Bj{\o}rstad, M.S. Espedal, and D.E. Keyes", publisher = "Domain Decomposition Press, Bergen, Norway", year = "1998", pages = "817-825", } Rune Teigland | Tel:+47 55 99 68 97 (office)| | Norsk Hydro | Tel:+47 55 95 32 35 (home) | (((( | Research Center | E-mail: |(oooo)| N-5020 Bergen, Norway | Rune.Teigland@nho.hydro.com | | Editor's Note: These will be integrated into the bibliography. See ------------- http://www.mgnet.org/mgnet-bib.html ------------------------------------------------------- Date: Feb 1999 From: Yousef Saad Subject: International Conference on Preconditioning Techniques SUBJECT: Intl. Conf. on preconditioning techniques FROM: Yousef Saad - U. of Minnesota * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * TITLE: 1999 INTERNATIONAL CONFERENCE ON PRECONDITIONING TECHNIQUES * * FOR LARGE SPARSE MATRIX PROBLEMS IN INDUSTRIAL APPLICATIONS * * * * DATE: June 10 - 12, 1999 * * * * PLACE: University of Minnesota, Hubert H. Humphrey Institute, * * Minneapolis, Minnesota * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Please consult the web-site http://www2.msi.umn.edu/Symposia/sparse99/main.html for detailed information. CONFERENCE TOPICS: o Incomplete factorization preconditioners o Domain decomposition preconditioners o Approximate inverse preconditioners o Multi-level preconditoners o Preconditioning techniques in optimization problems o Preconditioning techniques in finite element problems o Preconditioning techniques in image processing o Applications in Computational Fluid Dynamics (CFD) o Applications in computational finance o Multiphase subsurface flow applications o Applications in petroleum industry o Applications in semiconductor device simulation IMPORTANT: * Deadline for submitting extended abstracts has been extended to March 5th, 1999. Extended abstracts should be 7 pages maximum. mail to: Sparse-99 MSI 1200 Washington ave. S Minneapolis, MN 55415 Electronic submission encouraged. Send papers (post-script) to sparse99@msi.umn.edu. Editor's Note: Deadline extended to MONDAY, MARCH 8 (so write fast :-) ------------- ------------------------------ End of MGNet Digest **************************