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 7 (approximately July 31, 1999) Today's topics: Important Date AMG Tutorial on MGNet Research Studentship at Brunel University Two Papers (Guo Qingping et al) Paper by Achi Brandt and Dorit Ron Two Papers (Suely Oliveira et al) Cactus Computational Toolkit beta release Some of the new entries in the bibliography ------------------------------------------------------- Date: Fri, 31 Jul 1999 11:59:61 +0500 From: Craig DouglasSubject: Important Date August 15 Early registration for the 6th European Multigrid Conference: 260 Euros by check or bank transfer 1. By bank transfer to ASLK BANK, account nr 001-1950612-18 of Universiteit Gent, m entioning EMG99/P8730 and participant name (the code P8730 is extremely important to make sure that the payment arrives at its correct destination). The international bank code (swift code) is CGAKBEBB 2. By cheque addressed at UNIVERSITEIT GENT, Attn. Prof. E. DICK, Sint-Pietersnieuwstraat 41, 9000 GENT, BELGIUM. After August 15, 300 Euros See http://allserv.rug.ac.be/~edick/emg/register.html for online registration for the conference. ------------------------------------------------------- Date: Wed, 14 Jul 1999 12:04:16 +0200 (METDST) From: Christian Wrobel Subject: AMG Tutorial on MGNet I have a suggestion for the AMG Tutorial in http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Tutorials/amgtut_files. There are so many files, that getting them with "mget *" fails with "file list to long". It would be a great help if the whole directory would be tar'ed and gzipp'ed; then a single get is sufficient. Christian Wrobel Graduiertenkolleg fuer Modellierung und Diskretisierungsmethoden fuer Kontinua und Stroemungen (GKKS) Universitaet Stuttgart ICA 3 (Institut fuer Computer-Anwendungen) Allmandring 5b (Verfuegungsgebaeude) D-70569 Stuttgart Tel.: 0711 / 685 - 8240 Fax : 0711 / 685 - 8325 e-mail: christian@ica3.uni-stuttgart.de WWW: http://www.ica3.uni-stuttgart.de/~christia Editor's Note: I had assumed that everyone would use a web browser to look ------------- at the tutorial. I have placed a single gzipped tar file in http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Tutorials/amgtut.tgz See http://www.mgnet.org/mgnet-ccmm99.html or http://www.mgnet.org/mgnet-tuts.html ------------------------------------------------------- Date: Thu, 15 Jul 1999 12:32:01 +0100 (BST) From: Mike.Warby@brunel.ac.uk Subject: Research Studentship at Brunel University Research Studentship BICOM, Institute of Computational Mathematics, Brunel University Applications are invited for a three-year CASE research studentship at BICOM as part of the EPSRC funded project Computational Modelling of Thermoforming and In-Mould Decoration Processes In these processes thin polymeric sheets, on which patterns are printed, are deformed into specific shapes. The research will involve the modelling and numerical simulation of the deformation of the sheets. Of particular interest in the modelling is the prediction of the thickness distribution of the deformed structures and the prediction of the distortion of the patterns printed on the sheets. The project will be undertaken in close collaboration with two British manufacturing companies. Applicants should hold, or expect to obtain, a good first degree or Masters degree in a subject with a high mathematical content. The successful applicant will work in areas of computational solid mechanics associated with the above process. Previous knowledge of the areas is not essential as a programme of reading and instruction will be available. Interested persons should contact as soon as possible Professor J. R. Whiteman or Dr. M. K. Warby, BICOM, Dept. of Mathematics and Statistics, Brunel University, Uxbridge, Middlesex UB8 3PH, UK TEL: ++44 1895 203270 FAX: ++44 1895 203303 e-mails: john.whiteman@brunel.ac.uk or Mike.Warby@brunel.ac.uk ------------------------------------------------------- Date: Thu, 3 Jun 1999 23:07:20 +0800 From: "qpguo" Subject: Two Papers (Guo Qingping et al) Parallel Multi Grid Algorithm with Virtual Boundary Forecast Domain Decomposition Method for Solving Non-linear Heat Transfer Equation Guo Qingping Wuhan Transportation University Wuhan 430063, P. R. China Yakup Paker Queen Mary & West field College University of London E1 4NS U.K. Zhang Shesheng Wuhan Transportation University Wuhan 430063, P. R. China Dennis Parkinson Queen Mary & West field College University of London E1 4NS U.K. Wei Jialin Wuhan Transportation University Wuhan 430063, P. R. China Abstract This paper proposes a virtual boundary condition forecast method in parallel multi-grid algorithm design with domain decomposition for solving non-linear transient problem. Numerical results of non-linear transient heat transfer problem by the algorithm in a PVM network computing environment show that the algorithm has high parallel efficiency. Key words: Multi-Grid, Domain Decomposition, Virtual Boundary, Boundary Condition Forecast Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or access it at ------------- http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Papers/gpguo1.rtf * * * * * Virtual Boundary Condition Forecast Algorithm In Multigrid Domain Decomposition Parallel Computing Guo Qingping Wuhan Transportation University Wuhan 430063, P. R. China Yakup Paker Queen Mary & West field College University of London E1 4NS U.K. Zhang Shesheng Wuhan Transportation University Wuhan 430063, P. R. China Dennis Parkinson Queen Mary & West field College University of London E1 4NS U.K. Wei Jialin Wuhan Transportation University Wuhan 430063, P. R. China Abstract We propose a virtual boundary condition forecast algorithm for multi grid parallel computing, and derive a forecast function formula in this paper. Numerical results of one and two-dimension boundary condition problems obtained with the algorithm in a PVM network computing environment show that the algorithm has high parallel efficiency. Key words: Multi-Grid, Domain Decomposition, Virtual Boundary Forecast Editor's Note: See http://www.mgnet.org/mgnet-ccmm99.html or access it at ------------- http://www.mgnet.org/mgnet/Conferences/CopperMtn99/Papers/gpguo2.doc ------------------------------------------------------- Date: Thu, 15 Jul 1999 06:59:61 +0500 From: Craig Douglas Subject: Paper by Achi Brandt and Dorit Ron Renormalization Multigrid (RMG): Statistically Optimal Renormalization Group Flow and Coarse-to-Fine Monte Carlo Acceleration Achi Brandt and Dorit Ron Department of Applied Mathematics and Computer Science, Weizmann Institute of Science, Rehovot 76100, Israel Abstract New renormalization-group algorithms are developed with adaptive representations of the renormalized action which automatically express only significant interactions. As the amount of statistics grows, more interactions enter, thereby systematically reducing the truncation error. This allows statistically optimal calculation of thermodynamic limits, in the sense that it achieves accuracy e in just O(1/(e*e)) random number generations. There are practically no finite-size effects and the renormalization transformation can be repeated arbitrarily many times. Consequently, the desired fixed point is obtained and the correlation-length critical exponent $\nu$ is extracted.In addition, we introduce a new multiscale coarse-to-fine acceleration method, based on a multigrid-like approach. This general (non-cluster) algorithm generates independent equilibrium configurations without slow down. A particularly simple version of it can be used at criticality. The methods are of great generality; here they are demonstrated on the 2D Ising model. Key words. Ising model, Renormalization Multigrid, P+ probabilities, neighborhoods, criticalization, coarse-to-fine Monte Carlo acceleration, Compatible Monte Carlo, Post Relaxation. Editor's Note: See http://www.mgnet.org/mgnet-papers.html or access it at ------------- http://www.mgnet.org/mgnet/papers/Brandt/rmg299.ps.gz ------------------------------------------------------- Date: Fri, 06 Aug 1999 15:32:13 -0500 From: Suely Oliveira Subject: Two Papers (Suely Oliveira et al) Title: On the convergence rate of a Preconditioned Subspace Eigensolver Author: S. Oliveira (oliveira@cs.uiowa.edu). In this paper we present a proof of convergence for a preconditioned subspace method which shows the dependency of the convergence rate on the preconditioner used. This convergence rate depends only on the condition of the pre-conditioned system \( \kappa _{2}(MA) \) and the relative separation of the first two eigenvalues \( 1-\lambda _{1}/\lambda _{2} \). This means that, for example, multigrid preconditioners can be used to find eigenvalues of elliptic PDE's at a grid-independent rate. Note: this paper is to appear in Computing. Editor's Note: See http://www.mgnet.org/mgnet-papers.html or access it at ------------- http://www.mgnet.org/mgnet/papers/Oliveira/conv.ps.gz * * * * * TITLE: A Graph Based Davidson Algorithm for the Graph Partitioning Problem" Authors: M. Holzrichter and S. Oliveira. The problem of partitioning a graph such that the number of edges incident to vertices in different partitions is minimized, arises in many contexts. Some examples include its recursive application for minimizing fill-in in matrix factorizations and load-balancing for parallel algorithms. Spectral graph partitioning algorithms partition a graph using the eigenvector associated with the second smallest eigenvalue (Fiedler value) of a matrix called the {\em graph Laplacian}. The focus of this paper is the use graph theory to compute this eigenvector more quickly. Specifically we design a multigrid preconditioner coupled with the Davidson algorithm which works well for finding the Fiedler vector. This multigrid preconditioner uses ideas of graph coarsening, such as heavy edge matching, in its development. We anticipate that similar ideas can be used when developing Multigrid Algorithms for other unstructured problems. Editor's Note: See http://www.mgnet.org/mgnet-papers.html or access it at ------------- http://www.mgnet.org/mgnet/papers/Oliveira/graph.ps.gz ------------------------------------------------------- Date: Sun, 8 Aug 1999 20:42:10 -0500 (CDT) From: Ed Seidel Subject: Cactus Computational Toolkit beta release We are pleased to announce the public beta release of the Cactus Computational Toolkit 4.0! In advance of the Cactus 4.0 workshop, sponsored jointly by NCSA and AEI (Albert-Einstein-Institut), theToolkit, complete with documentation and tutorials, is now publicly accessible at http://www.cactuscode.org. In a nutshell, the Toolkit provides a modular, portable, and manageable environment for collaboratively developing high-performance multidimensional numerical simulations. It allows one, with only a working knowledge of Fortran or C, to plug application specific computational modules into the framework, allowing one to make use of the following features: Powerful Application Programming Interface User modules (thorns) plug-into compact core (flesh) Configurable interfaces, schedules and parameters Advanced Computational Toolkit Accessible MPI-based parallelism for finite difference grids Access to a variety of supercomputing architectures and clusters Several parallel I/O layers Fixed and Adaptive mesh refinement under development Elliptic solvers Metacomputing, distributed computing and visualization tools Collaborative Development Enables sharing code base TestSuite checking technology Exhaustive Numerical Relativity and Astrophysical Applications Black Hole coalescence Neutron star collisions Other cataclysms... We encourage people to check it out and give feedback about the code or the documentation as we prepare to release the final version. We also encourage you to attend the workshop, scheduled for Sept. 27-Oct. 1, 1999, at NCSA in Champaign, IL. Please see the first workshop announcement at http://www.ncsa.uiuc.edu/SCD/Training/CactusAnnounce.html for further details. A second announcement with a more detailed agenda will be made by the end of August. We remind potential attendees to email us to register at workshop99@cactuscode.org. If you do not wish to receive further emails on Cactus, please email us and we will remove your name from our mailing lists. On the other hand, please pass this announcement on to others who may have interest! Thanks, Ed Seidel Ed Seidel Max-Planck-Institut fuer Gravitationsphysik and University of Illinois Summer address: Phone: (217) 244-1976 Fax: (217) 244-2909 Mail: NCSA U of Illinois 605 E. Springfield Ave Champaign, IL 61820 USA ------------------------------------------------------- Date: Tue, 9 Aug 1999 14:42:12 +0500 From: Craig Douglas Subject: Some of the new entries in the bibliography The latest version is dated August 10, 1999, has 3341 entries, and is 169 pages long. Here are some recent new entries. As usual, please send additions and corrections. Editor's Note: See http://www.mgnet.org/mgnet-bib.html ------------- REFERENCES [1] R. E. Bank and S. Gutsch, The generalized hierarchical ba- sis two-level method for the convection-diffusion equation on a regular grid, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Science and Engineering, Berlin, 1998, Springer, pp. 1-20. [2] A. Brandt and C. H. Venner, Multilevel evaluation of in- tegral transforms on adaptive grids, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Science and Engineering, Berlin, 1998, Springer, pp. 21-44. [3] H.-J. Bungartz and Th. Dornseifer, Sparse grids: re- cent developments for elliptic partial differential equations, in Multigrid Methods V, vol. 3 of Lecture Notes in Com- putational Science and Engineering, Berlin, 1998, Springer, pp. 45-70. [4] M. Czajkowski, Solution of an initial control problem for the shallow water equations by a multi-grid method, in 5th Euro- pean Multigrid Conference Special Topics and Applications, University of Stuttgart, Stuttgart, 1998, pp. 5-17. [5] J. E. Dendy and H. Tchelepi, Multigrid applied to implicit well problems, in 5th European Multigrid Conference Special Topics and Applications, University of Stuttgart, Stuttgart, 1998, pp. 18-34. [6] V. V. Denissenko, The mutligrid method for symmetrized boundary value problems of diffusion in moving medium, in 5th European Multigrid Conference Special Topics and Ap- plications, University of Stuttgart, Stuttgart, 1998, pp. 35- 46. [7] P. Deuflhard and M. Weiser, Global inexact Newton mul- tilevel FEM for nonlinear elliptic equations, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Sci- ence and Engineering, Berlin, 1998, Springer, pp. 71-89. [8] C. C. Douglas, S. Malhotra, and M. H. Schultz, Paral- lel multigrid with ADI-like smoothers in two dimernsions, in 5th European Multigrid Conference Special Topics and Ap- plications, University of Stuttgart, Stuttgart, 1998, pp. 47- 57. [9] R. Enander and E. Sterner, Analysis of internal bound- ary conditions and communication strategies for multigrid multiblock methods, in 5th European Multigrid Conference Special Topics and Applications, University of Stuttgart, Stuttgart, 1998, pp. 58-73. [10] L. V. Gilyova and V. V. Shaidurov, A cascadic mutigrid algorithm in finite element method for an indefinte-sign el- liptic problem, in 5th European Multigrid Conference Special Topics and Applications, University of Stuttgart, Stuttgart, 1998, pp. 74-89. [11] Th. Gjesdal, Accuracy and convergence of defect correction in an incompressible multigrid solver basewd onpressure correc- tion smoothers, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Science and Engineering, Berlin, 1998, Springer, pp. 90-104. [12] W. Hackbusch and G. Wittum, 5th European Multigrid Conference Special Topics and Applications, University of Stuttgart, Stuttgart, 1998. [13] ______, Multigrid Methods V, vol. 3 of Lecture Notes in Compu- tational Science and Engineering, Springer, Berlin, 1998. [14] M. G. Hackenberg, W. Joppich, and S. Mijalkovic, A paralle multigrid environment for coupled problems on time- dependent structures, in 5th European Multigrid Conference Special Topics and Applications, University of Stuttgart, Stuttgart, 1998, pp. 90-100. [15] W. Heinrichs, Operator splitting for the unsteady Stokes equa- tions, in 5th European Multigrid Conference Special Topics and Applications, University of Stuttgart, Stuttgart, 1998, pp. 101-112. [16] P. W. Hemker, B. Koren, and J. Noordmans, 3D multi- grid on partially ordered sets of grids, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Science and Engineering, Berlin, 1998, Springer, pp. 105-124. [17] M. Holzrichter and S. Oliveira, A graph based Davidson algorithm for the graph partitioning problem, Int. J. Found. Comp. Sci., 10 (1999), pp. 225-247. [18] JSch"oberl, Robust multigrid preconditioning for parameter- dependent problems I: the Stokes case, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Science and Engineering, Berlin, 1998, Springer, pp. 260-2275. [19] M. Jung, Parallel multi-level solvers for elliptic boundary value problems in three-dimensional domains, in Multigrid Meth- ods V, vol. 3 of Lecture Notes in Computational Science and Engineering, Berlin, 1998, Springer, pp. 125-139. [20] B. N. Khoromskij and G. Wiitum, Robust interface reduc- tion for highly anisotropic elliptic equations, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Sci- ence and Engineering, Berlin, 1998, Springer, pp. 140-156. [21] F. Kickinger, Algebraic multigrid for discrete elliptic second- order problems, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Science and Engineering, Berlin, 1998, Springer, pp. 157-172. [22] R. Kornhuber, On robust multigrid methods for non-smooth variational problems, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Science and Engineering, Berlin, 1998, Springer, pp. 173-188. [23] A. Krechel and K. St"uben, Operator dependent interpola- tion in algebraic multigrid, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Science and Engineering, Berlin, 1998, Springer, pp. 189-211. [24] C. W. Oosterlee, F. J. Gaspar, T. Washio, and R. Wienands, Fast multigrid solvers for higher order up- wind discretizations of convection-dominated problems, in Multigrid Methods V, vol. 3 of Lecture Notes in Compu- tational Science and Engineering, Berlin, 1998, Springer, pp. 212-224. [25] J. Piquet and X. Vasseur, Comparisions between precondi- tioned BICGSTAB and a multigrid method for the resolution of the pressure equation in a Navier-Stokes solver, in Multi- grid Methods V, vol. 3 of Lecture Notes in Computational Science and Engineering, Berlin, 1998, Springer, pp. 225- 242. [26] A. Quarteroni and A. Valli, Domain Decomposition Meth- ods for Partial Differential Equations, Oxford University Press, Oxford, 1999. [27] A. Reusken, Approximate cyclic reduction preconditioning, in Multigrid Methods V, vol. 3 of Lecture Notes in Compu- tational Science and Engineering, Berlin, 1998, Springer, pp. 243-259. [28] A. Schuller, C. W. Ooster- lee, H. Ritzdorf, H. Schwichtenberg, B. Steckel, and J. Wu, Parallelization and adapative grids for indus- trial areadynamic multigrid codes, in 5th European Multi- grid Conference Special Topics and Applications, University of Stuttgart, Stuttgart, 1998, pp. 113-124. [29] V. Shultz and G. Wittum, Multigrid optimization methods for stationary problems I: the Stokes-type case, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Sci- ence and Engineering, Berlin, 1998, Springer, pp. 276-288. [30] J. Steelent, E. Dick, and S. Pattijn, Analysis of multigrid efficiency for viscous low mach mumber flows, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Sci- ence and Engineering, Berlin, 1998, Springer, pp. 289-305. [31] R. Stevenson, Piecewise linear (pre-)wavelets on non-uniform meshes, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Science and Engineering, Berlin, 1998, Springer, pp. 306-319. [32] Ch. Wagner and G. wittum, Filtering decompositions with respect to adaptive test vectors, in Multigrid Methods V, vol. 3 of Lecture Notes in Computational Science and Engi- neering, Berlin, 1998, Springer, pp. 320-334. [33] T. Washio and K. Oosterlee, Krylov subspave accelration for nonlinear mutigrid schemes, in 5th European Multigrid Conference Special Topics and Applications, University of Stuttgart, Stuttgart, 1998, pp. 125-137. ------------------------------ End of MGNet Digest **************************