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@ccs.uky.edu) Volume 8, Number 3 (approximately March 31, 1998) Today's topics: Job Open at Oxford Postdoc position at CCMA of Penn State PLTMG8.0 ETNA's Copper Mountain Proceedings. Paper by Duff and Koster 3 Papers on Algebraic Multilevel Methods by Notay 16 Papers added to 5th Copper Mountain Iterative Methods Area ------------------------------------------------------- From: "Mike Rudgyard" Date: Fri, 27 Mar 1998 14:15:12 +0000 Subject: Job Open at Oxford If anyone is finishing their PhD/Post-doc, I have a post in parallel computing (involving multigrid and distributed partitioning) here at Oxford. See http://www.comlab.ox.ac.uk/oucl/jobs/pld.html ------------------------------------------------------- Date: Fri, 27 Mar 1998 21:33:29 -0500 From: Jinchao Xu Subject: Postdoc position at CCMA of Penn State Contingent upon final approval of funding, we will have a postdoc position available from Fall 1998 in the Center for Computational Matheamtics and Applications of Penn State University (http://www.math.psu.edu/ccma/). Applicants must have a strong background in numerical methods for partial differential equations (especially finite element methods) and programming experiences. Good knowledge on multigrid methods is desirable. Interested applicants should send application materials ASAP to Professor Jinchao Xu Department of Mathematics Pennsylvania State University University Park, PA 16802 Email applications (sent to xu@math.psu.edu) are encouraged. Email message may include application materials or a letter indicating an URL address for accessing other detailed application materials. Penn State is an equal opportunity/affirmative action employer, and especially encourages applications from women and minorities. ------------------------------------------------------- Date: Mon, 6 Apr 1998 13:33:13 -0700 (PDT) From: "Randolph E. Bank" Subject: Pltmg8.0 PLTMG 8.0 is a package for solving elliptic partial differential equations in general regions of the plane. It is based on continuous piecewise linear triangular finite elements, and features adaptive local mesh refinement, multigraph iteration, and pseudo-arclength continuation options for parameter dependencies. The package includes an initial mesh generator and several graphics packages. Full documentation is provided in PLTMG: A Software Package for Solving Elliptic Partial Differential Equations - Users' Guide 8.0 (ISBN 0-89871-409-5), available from SIAM Publications. PLTMG is provided as Fortran (and a little C) source code, in both single and double precision versions. The included X-Windows GUI uses the default Athena Widget set, and makes calls to standard library routines of the X-Windows system, which must be loaded along with the PLTMG software. PLTMG is available from Netlib and MGNet. Editor's Note: The previous version (7.2) is still on MGNet, but will be ------------- deleted eventually. You can find version 8.0 either in www.mgnet.org/mgnet-codes.html or in mgnet/Codes/pltmg. ------------------------------------------------------- Date: Fri, 13 Mar 1998 15:51:16 -0500 From: ETNA Subject: ETNA's Copper Mountain Proceedings. The Editors of Electronic Transactions on Numerical Analysis, ETNA, are proud to announce the publication of the Proceedings of the Eighth Copper Mountain Conference on Multigrid Methods held April 6-11, 1997, at the Copper Mountain Resort in Colorado, as a special issue of ETNA . This issue, Volume 6, contains 290 pages of 19 high-quality articles dealing with multigrid and other multilevel techniques. ETNA can be found on the web at URL http://etna.mcs.kent.edu. There is no charge to access ETNA, and all ETNA articles are available in both PostScript and PDF formats. Editor's Note: Here is what you find for the table of contents: ------------- Special Issue on Multilevel Methods This is a special issue of ETNA on multilevel methods for numerical solution of partial differential equations and other complex mathematical problems. The papers here consist of results presented at the Eighth Copper Mountain Conference on Multigrid Methods held April 6-11, 1997, at Copper Mountain Resort in Colorado. There were 60 talks at the meeting, counting special workshop and circus sessions, with about 100 attendees. To quote the MGNet 'Postcard' from Craig Douglas: "For the first time in years, there were no parallel sessions for talks, giving the conference the type of intimacy found in the GAMM parallel multigrid workshops held in Germany for many years and most recently in Austria. Two years ago there were many newcomers to the Copper Mountain conference. Once again this was the case. In part this is due to the large number of graduate students and fresh Ph.D.'s who have attended both conferences." The conference series continues to reflect the maturation of the multigrid field. There were many talks on basic theory and algorithms, important practical applications, parallelization, and other computational issues. The papers in this special issue illustrate this evolution, but they also suggested the seemingly endless number of research questions that remain. Each of the following papers was subjected to a critical refereeing process, upholding the high standards of the ETNA editorial board. We extend our sincerest thanks to following members of our Conference Committee who served as guest editors for this special issue: Joel Dendy Los Alamos National Lab Craig Douglas University of Kentucky Van Henson Lawrence Livermore National Lab Jim Jones Lawrence Livermore National Lab Kirk Jordan IBM Duane Melson NASA Langley Research Center Seymour Parter University of Wisconsin Joseph Pasciak Texas A & M John Ruge University of Colorado at Boulder Irad Yavneh Technion We also wish to thank the University of Colorado, the Society for Industrial and Applied Mathematics, and the Institute for Algorithms and Scientific Computing of the GMD for organizational support. Finally, we are especially indebted to Fred Howes of the Department of Energy, Michael Steuerwalt of the National Science Foundation, Kirk Jordan of IBM, and Ulrich Trottenberg of the Institute for Algorithms and Scientific Computing of the GMD for financial support. Steve McCormick and Tom Manteuffel, University of Colorado, Boulder ------------------------------------------------------------------------ The Gauss Center Research in Multiscale Scientific Computation 1 Achi Brandt Local Error Estimates and Adaptive Refinement for First-Order System Least Squares (FOSLS) 35 Markus Berndt, Thomas A. Manteuffel, and Stephen F. McCormick Experiences With Negative Norm Least-Square Methods for the Navier-Stokes Equations 44 P. Bochev A Multigrid Algorithm for Higher Order Finite Elements on Sparse Grids 63 Hans-Joachim Bungartz The Analysis of Intergrid Transfer Operators and Multigrid Methods for Nonconforming Finite Elements 78 Zhangxin Chen Semicoarsening Multigrid for Systems 97 J.E. Dendy, Jr. Multigrid Algorithm with Conditional Coarsening for the Non-aligned Sonic Flow 106 Boris Diskin A Comparison of Multilevel Adaptive Methods for Hurricane Track Prediction 120 Scott R. Fulton Multigrid Method for H(DIV) in Three Dimensions 133 R. Hiptmair Asymptotic Stability of a 9-Point Multigrid Algorithm for Convection-Diffusion Equations 153 Jules Kouatchou Wave-Ray Multigrid Method for Standing Wave Equations 162 A. Brandt and I. Livshits Directional Coarsening and Smoothing for Anisotropic Navier-Stokes Problems 182 Dimitri J. Mavriplis A Two-level Discretization Method for the Stationary MHD Equations 198 W. J. Layton, A. J. Meir, and P. G. Schmidt A Stable Multigrid Strategy for Convection-Diffusion Using High Order Compact Discretization 211 Anand L. Pardhanani, William F. Spotz, and Graham F. Carey A Parallel Multigrid Method Using the Full Domain Partition 224 William F. Mtichell A Multigrid Smoother for High Reynolds Number Flows 234 Erik Sterner Fast Solution of MSC/NASTRAN Sparse Matrix Problems Using A Multilevel Approach 246 C. A. Thole, S. Mayer, and A. Supalov A Comparison of Multilevel Methods for Total Variation Regularization 255 P. S. Vassilevski and J. G. Wade Krylov Subspace Acceleration For Nonlinear Multigrid Schemes 271 T. Washio and C. W. Oosterlee ------------------------------------------------------- Date: Sun, 8 Mar 1998 21:09:07 GMT From: I.Duff@rl.ac.uk (Iain Duff) Subject: Paper by Duff and Koster The Design and Use of Algorithms for Permuting Large Entries to the Diagonal of Sparse Matrices Iain S. Duff and Jacko Koster Department of Computation and Information Atlas Centre Rutherford Appleton Laboratory Oxon OX11 0QX England Abstract We consider techniques for permuting a sparse matrix so that the diagonal of thepermuted matrix has entries of large absolute value. We discuss various criteria for this and consider their implementation as computer codes. We then indicate several cases where such a permutation can be useful. These include the solution of sparse equations by a direct method and by an iterative technique. We also consider its use in generating a preconditioner for an iterative method. We see that the effect of these reorderings can be dramatic although the best {\it a priori} strategy is by no means clear. Editor's Note: in mgnet/papers/Duff-Koster/permute.ps.gz or ------------- http://www.mgnet.org/mgnet-papers.html. ------------------------------------------------------- Date: Thu, 2 Apr 1998 12:45:17 +0200 (MET DST) From: Yvan NOTAY Subject: 3 Papers on Algebraic Multilevel Methods by Notay I recently wrote 3 papers on algebraic multilevel methods. Title, abstract and ftp & http references are given below. I suggest you to include this in the next MG-Digest, and I further encourage you to download the files, so as to make them available on the MGNet preprint service too. Many thanks in advance. Sincerely, Yvan Notay Editor's Note: Uploaded to MGNet; see www.mgnet.org/mgnet-papers.html. ------------- The files are in mget/papers/Notay. <==========================================================> > Yvan NOTAY | < < Universite Libre de Bruxelles | email : ynotay@ulb.ac.be > > Service de Metrologie | < < Nucleaire (CP 165) | tel : (32) 2 650 36 70 > > 50 av. F.D.Roosevelt | fax : (32) 2 650 45 34 < < B-1050 Bruxelles BELGIUM | > >==========================================================< < URL http://homepages.ulb.ac.be/~ynotay > >==========================================================< Using approximate inverses in algebraic multilevel methods ---------------------------------------------------------- Y. Notay http://homepages.ulb.ac.be/~ynotay ftp://mnserver.ulb.ac.be/pub/reports/apinv.ps.gz To appear in Numer. Math. abstract -------- This paper deals with the iterative solution of large sparse symmetric positive definite systems. We investigate preconditioning techniques of the two-level type that are based on a block factorization of the system matrix. Whereas the basic scheme assumes an exact inversion of the submatrix related to the first block of unknowns, we analyze the effect of using an approximate inverse instead. We derive condition number estimates that are valid for any type of approximation of the Schur complement and that do {\em not} assume the use of the hierarchical basis. They show that the two-level methods are stable when using approximate inverses based on modified ILU techniques, or explicit inverses that meet some row-sum criterion. On the other hand, we bring to the light that the use of standard approximate inverses based on convergent splittings can have a dramatic effect on the convergence rate. These conclusions are numerically illustrated on some examples. Optimal order preconditioning of finite difference matrices ----------------------------------------------------------- Yvan Notay http://homepages.ulb.ac.be/~ynotay ftp://mnserver.ulb.ac.be/pub/reports/ganmn_ps/ganmn9702.ps.gz Report GANMN 97-02 abstract -------- A new multilevel preconditioner is proposed for the iterative solution of two dimensional discrete second order elliptic PDEs. It is based a recursive block incomplete factorization of the system matrix partitioned in a two-by-two block form, in which the submatrix related to the first block of unknowns is approximated by a MILU(0) factorization, and the Schur complement computed from a diagonal approximation of the latter submatrix. It is shown that this technique, combined with a simple $W$ cycle scheme, leads to optimal order preconditioning of five point finite difference matrices. This result holds independently of possible anisotropy or jumps in the PDE coefficients as long as the latter are piecewise constant on the coarsest mesh. Numerical results illustrate the efficiency and the robustness of the proposed method. Optimal V cycle algebraic multilevel preconditioning ---------------------------------------------------- Y. Notay http://homepages.ulb.ac.be/~ynotay ftp://mnserver.ulb.ac.be/pub/reports/ganmn_ps/ganmn9705.ps.gz Report GANMN 97-05 abstract -------- We consider algebraic multilevel preconditioning methods based on the recursive use of a $2 \times 2$ block incomplete factorization procedure in which the Schur complement is approximated by a coarse grid matrix. As is well known, for discrete second order elliptic PDEs, optimal convergence properties are proved for such basic two-level schemes under mild assumptions on the PDE coefficients, but their recursive use in a simple V cycle algorithm does generally not lead to optimal order convergence. In the present paper, we analyze the combination of these techniques with a smoothing procedure much similar to the one used in standard multigrid algorithms, except that smoothing is not required on the finest grid. Theoretical results prove optimal convergence properties for the V cycle under an assumption similar to the ``approximation property" of the classical multigrid convergence theory. On the other hand, numerical experiments show that, for both 2D and 3D problems, using rather simple smoothing strategies suffices to make the condition number close to that of the two-level method. ------------------------------------------------------- Date: Tue, 31 Mar 1998 12:31:11 -0500 From: Craig Douglas Subject: 16 Papers added to 5th Copper Mountain Iterative Methods Area The following papers or (roughly) 7 page extended abstracts were added to the virtual proceedings of the Fifth Copper Mountain Iterative Methods Conference. They can be found through www.mgnet.org/mgnet-conferences.html. A list of attendees and all of the abstracts can also be found there. M. Adams A Parallel Maximal Independent Set Algorithm A. Brandt, M. Israeli, I. Yavneh, and A. Siegel Multigrid Solution of an Elliptic Boundary-Value Problem with Integral Constraints R. Bridson and W.-P. Tang Ordering for the Factored Approximate Inverse Preconditioners W. K. Ching Circulant Approximation for Preconditioning in Stochastic Automata Networks T. Dayar and W. J. Stewart Comparison of Partitioning Techniques for Two-Level Iterative Solvers on Large, Sparse Markov Chains D. S. Daoud and T. Gungormus On the Schwarz Alternating Procedure with a Polynomial Preconditioning Conjugate Gradient A. Knyazev Preconditioned Eigensolvers - an Oxymoron? D. Loghin Green's Functions For Preconditioning W.-S. Luk, J. Janssen, and S. Vandewalle Application of determinant Maximization Programming to the SOR and Chebyshev Methods for Complex Linear Systems S. Oliveira Convergence and Parallelization of a Preconditioned Algorithm for Eigenvalues J. Rahola Iterative Solution of Dense Linear Systems A. C. Robinson and M. A. Christon Using AZTEC to Solve the Linear System Associated with the Three-dimensional Magnetohydrodynamic (MHD) Modeling in ALEGRA M. Seaid A Fast Monotone Iterative Method for Nonlinear Reaction-Diffusion Systems Y. Shapira A Multi-Level Method for Sparse Linear Systems H. Van der Vorst Preconditioning for Eigenproblems C. Vuik, G. Segal, and K. Meijerink An Efficient CG Method for Layered Problems with Large Contrasts in the Coefficients Editor's Note: Files in mgnet/Conferences/CMCIM98. ------------- ------------------------------ End of MGNet Digest **************************