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 WWW Sites: 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.hpcc.jp/mirrors/mgnet or http://www.tat.physik.uni-tuebingen.de/~mgnet Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) Volume 13, Number 8 (approximately August 31, 2003) Today's topics: Adding Preprint/Code Reference to MGNet New Book "Matrix-Based Multigrid" (Kluwer) New Book at SIAM on Parallel Elliptic PDE Solving Workshop in Graz Workshop on Adaptive Parallel Computing Postdoctoral Position at University of Kentucky ------------------------------------------------------- Date: Thu, 21 Aug 2003 15:46:33 -0500 From: Scott HawleySubject: Adding Preprint/Code Reference to MGNet I am writing to inform you of a paper written by myself and a colleague. Title: Tips for implementing multigrid methods on domains containing holes Authors: Scott H. Hawley, Richard A. Matzner Contact: shawley@physics.utexas.edu Comments: 18 pages, 11 figures, LaTeX Abstract: As part of our development of a computer code to perform 3D "constrained evolution" of Einstein's equations in 3+1 form, we discuss issues regarding the efficient solution of elliptic equations on domains containing holes (i.e., excised regions), via the multigrid method. We consider as a test case the Poisson equation with a nonlinear term added, as a means of illustrating the principles involved, and move to a 3-dimensional problem similar to the Hamiltonian constraint that arises in black hole data setting. Using our vertex-centered multigrid code, we demonstrate that it is possible to obtain globally second-order accurate solutions of elliptic equations over domains containing holes, in two and three spatial dimensions. Keys to the success of this method are the choice of the restriction operator near the holes and definition of the location of the inner boundary. In some cases (e.g. two holes in two dimensions), more and more smoothing may be required as the mesh spacing decreases to zero; however for the resolutions currently of interest to many numerical relativists, it is feasible to maintain second-order convergence by concentrating smoothing (spatially) where it is needed most. This paper, and our publicly available source code, are intended to serve as semi-pedagogical guides for those who may wish to implement similar schemes. PostScript: http://arxiv.org/ps/gr-qc/0306122 PDF: http://arxiv.org/pdf/gr-qc/0306122 Other formats: http://arxiv.org/format/gr-qc/0306122 I also have a publicly available, fairly simple and fairly well documented Fortran code which illustrates the principles involved. This is available at http://wwwrel.ph.utexas.edu/~shawley/export/robin3d.tar.gz You are welcome to link to this under "Free Software" if you like, however I have no preference as to whether you do this or not. If you do, I suppose it should be called Robin3D, and there should be a description like "A simple 3D multigrid code (for scalar equations), which handles domains with holes. For those interested in how to implement such a scheme. It also implements Robin outer boundary conditions; hence the name. Based on a 2D FAS solver by Matthew Choptuik." Dr. Scott H. Hawley, Office RLM 9.206, http://wwwrel.ph.utexas.edu/~shawley Center for Relativity, Dept of Physics Tel: +1-512-471-5426 Univ. of Texas at Austin, Austin TX 78712 USA Fax:+1-512-471-0890 ------------------------------------------------------- Date: Fri, 22 Aug 2003 00:57:04 +0300 (IDT) From: Yair Shapira Subject: New Book "Matrix-Based Multigrid" (Kluwer) Matrix-Based Multigrid Theory and Applications by Yair Shapira Computer Science Dept., Technion, Haifa, Israel Book Series: NUMERICAL METHODS AND ALGORITHMS : Volume 2 This book is an introduction and analysis of the multigrid approach for the numerical solution of large sparse linear systems arising from the discretization of elliptic partial differential equations. It gives special attention to the powerful matrix-based-multigrid approach, which is particularly useful for problems with variable coefficients and nonsymmetric and indefinite problems. The approach used here applies not only to model problems on rectangular grids but also to more realistic applications with complicated grids and domains and discontinuous coefficients. The discussion draws connections between multigrid and other iterative methods such as domain decomposition. The theoretical background provides insight about the nature of multigrid algorithms and how and why they work. The theory is written in simple algebraic terms, and therefore, requires preliminary knowledge only in basic linear algebra and calculus. Audience: Researchers, engineers, students, and others who are interested in the numerical solution of partial differential equations. Kluwer Academic Publishers, Boston Hardbound, ISBN 1-4020-7485-9 July 2003, 248 pp. EUR 117.00 / USD 115.00 / GBP 74.00 http://www.wkap.nl/prod/b/1-4020-7485-9 TABLE OF CONTENTS Chapter 1: The Multilevel--Multiscale Approach The Multilevel--Multiscale Concept, The Integer Number, The Division Algorithm, The Greatest-Common-Divider Algorithm, Multilevel Refinement, Examples from Computer Science, Self Similarity, The Wavelet Transform, Mathematical Induction and Recursion, The Product Algorithm, Preliminary Notations and Definitions, Application to Pivoting, The Fourier Transform PART I: THE PROBLEM AND SOLUTION METHODS Chapter 2: PDEs and Discretization Methods Standard Lemmas about Symmetric Matrices, Elliptic Partial Differential Equations, The Diffusion Equation, The Finite-Difference Discretization Method, Finite Differences for the Poisson Equation, The Finite-Volume Discretization Method, The Finite-Element Discretization, Structured and Unstructured Grids Chapter 3: Iterative Linear-System Solvers Iterative Sparse-Linear-System Solvers, The Jacobi, Gauss-Seidel, and Kacmarz Relaxation Methods, Reordering by Colors, Cache-Oriented Reordering, Symmetric Gauss-Seidel Relaxation, The Preconditioned Conjugate Gradient (PCG) Method, Incomplete LU Factorization (ILU), Parallelizable ILU Relaxation, Parallelizable Gauss-Seidel Relaxation Chapter 4: Multigrid Algorithms The Two-Grid Method, The Multigrid Method, Geometric Multigrid, Matrix-Based Multigrid, Algebraic Multigrid PART II: MULTIGRID FOR STRUCTURED GRIDS Chapter 5: The AutoMUG Method Properties of the AutoMUG Method, Cyclic Reduction, The 2-D Case, The AutoMUG Method, The AutoMUG(q) Method Chapter 6: Applications in Image Processing The Denoising Problem, The Denoising Algorithm for Grayscale Images, The Denoising Algorithm for RGB Color Images, Examples Chapter 7: The Black-Box Multigrid Method Definition of BBMG, Application to Problems with Discontinuous Coefficients Chapter 8: The Indefinite Helmholtz Equation The Helmholtz Equation, Adequate Discretization of the Indefinite Helmholtz Equation, Definition of BBMG2, Computational Two-Level Analysis, Multiple Coarse-Grid Corrections, The Size of the Coarsest Grid, Numerical Examples Chapter 9: Matrix-Based Semi-Coarsening Flow of Information in Elliptic Problems, Sequential Block-ILU Factorization, The Domain Decomposition Solver, Reordered Block-ILU Factorization, Matrix-Based Semi-Coarsening Multigrid Method, A Deblurring Problem PART III: MULTIGRID FOR SEMI-STRUCTURED GRIDS Chapter 10: Matrix-Based Multigrid for Locally Refined Meshes Locally Refined Meshes, Multigrid and Hierarchical-Basis Linear-System Solvers, The Two-Level Method, Matrix-Induced Inner Products and Norms, Properties of the Two-Level Method, Isotropic Diffusion Problems, The Multi-Level Method, Upper Bound for the Condition Number, The V(1,1), AFAC, and AFACx Cycles, Scaling the Coefficient Matrix, Black-Box Multigrid Version for Semi-Structured Grids, Conclusions PART IV: MULTIGRID FOR UNSTRUCTURED GRIDS Chapter 11: Domain Decomposition Advantages of the Domain Decomposition Approach, The Domain Decomposition Multigrid Method, Upper Bound for the Condition Number, High-Order Finite-Element and Spectral-Element Schemes Chapter 12: Algebraic Multilevel Method The Need for Algebraic Multilevel Methods, The Algebraic Multilevel Method, Properties of the Two-Level Method, Properties of the Multilevel Method, Upper Bound for the Condition Number, Adequate Discretization of Highly Anisotropic Equations, Application to the Maxwell Equations, The Convection-Diffusion Equation, The Approximate-Schur-Complement Method, Towards Semi-Algebraic Multilevel Methods Chapter 13: Conclusions Appendix A: C++ Framework for Unstructured Grids ------------------------------------------------------- Date: Fri, 29 Aug 2003 10:03:21 +0200 From: Gundolf Haase Subject: New Book at SIAM on Parallel Elliptic PDE Solving The following book is available now: Craig C. Douglas, Gundolf Haase, and Ulrich Langer: "A Tutorial on Elliptic PDE Solvers and Their Parallelization", SIAM Series Software, Environments, and Tools, 2003, ISBN 0-89871-541-5 (http://ec-securehost.com/SIAM/SE16.html) This tutorial serves as a first introduction into the basic concepts of solving partial differential equations using parallel numerical methods. The ability to understand, develop, and implement parallel PDE solvers requires not only some basic knowledge in PDEs, discretization methods, and solution techniques, but also some knowledge about parallel computers, parallel programming, and the run-time behaviour of parallel algorithms. Our tutorial provides this knowledge in just 8 short chapters. The authors kept the examples simple so that the parallelization strategies are not dominated by technical details. The practical course for the tutorial can be downloaded from the internet, see http://www.numa.uni-linz.ac.at/books/ http://www.mgnet.org/books/Douglas-Haase-Langer Gundolf Haase ------------------------------------------------------- Date: Tue, 02 Sep 2003 10:30:30 +0200 From: Alfio Borzi Subject: Workshop in Graz Dear Collegues, We would like to inform you that the program of the Workshop Advances in Numerical Algorithms is now ready. Please have a look at the homepage http://www.kfunigraz.ac.at/imawww/borzi/workshop/index_num.html Salutissimi Alfio Borzi and Karl Kunisch Advances in Numerical Algorithms Program Wednesday 8:00-9:00 Registration 9:00-9:30 K. Kunisch Welcome & Opening 9:40-10:10 S.G. Nash Model problems for the multigrid optimization of systems governed by differential equations 10:40-11:10 F. Rendl Computational experience with large-scale semidefinite programming problems 11:20-11:50 S.I. Petrova Mesh adaptivity methods for shape optimization problems 12:00-12:30 B. Vexler A posteriori error estimation for finite element discretization of parameter identification problems 14:30-15:00 A. Kunoth Adaptive wavelets methods for semilinear-quadratic control problems 15:10-15:40 M. Hinze A new discretization concept in control constrained pde control and its numerical realization 16:10-16:40 G. Stadler Semi-smooth Newton and augmented Lagrangian methods for friction and contact problems 16:50-17:20 B. Kaltenbacher Material parameter identification of piezoelectricity and magnetics Thursday 9:00-9:30 C. Pflaum Advances in the numerical simulation of lasers 9:40-10:10 M. Wabro Coupled algebraic multigrid methods for the Navier-Stokes equations 10:40-11:10 K. Mikula Finite volume methods in image smoothing and segmentation 11:20-11:50 S. Keeling Image registration and interpolation by optical flow with maximal rigidity 12:00-12:30 I. Yavneh Multi-level algorithms for some image-processing problems 14:30-15:00 C.C. Douglas Virtual telemetry for dynamic data-driven application simulations 15:10-15:40 S. Ta'asan Multiscale modeling of biological networks 16:10-16:40 G. Haase A two level recursive calculation of coarse matrices in AMG 16:50-17:20 U. Ruede Adaptive PDE solvers for supercomputers Friday 9:00-9:30 B. Basara Turbulence modelling from the perspective of the commercial CFD 9:40-10:10 A. Valli Mixed and 'hybrid' finite element approximation of eddy-current problems 10:40-11:10 W. Hackbusch The efficient numerical treatment of the matrix equation of Ljapunov and Riccati type 11:20-11:50 C. Gaspar Fast interpolation techniques and meshless methods 12:00-12:30 B. Wohlmuth Domain decomposition techniques based on fictious domains 14:30-15:00 C. Schmeiser Models for the chemosensory movement of leucocytes 15:10-15:40 E. Weinmueller Numerical solution of singular boundary value problems in ODEs. 16:10-16:40 V. Schulz Simultaneous optimization in applications 16:50-17:20 J. Schoeberl Multigrid preconditioning for parameter dependent problems Saturday 9:00-9:30 G. Wittum tba 9:40-10:10 A. Arnold Transparent boundary conditions for quantum-waveguides 10:40-11:10 L. Blank Wavelet and Schur complement based preconditioning with an application in state estimation 11:20-11:50 C. Burstedde Numerical results for a wavelet discretization of a linear-quadratic elliptic control problem 12:00-12:30 F. Lenzen Automatic detection of gravitational arcs in astronomical data using anisotropic diffusion and segmentation 12:40-13:00 Closing ------------------------------------------------------- Subject: Workshop on Adaptive Parallel Computing From: Jochen Hittler Date: Thu, 21 Aug 2003 12:16:59 +0200 Workshop on Adaptive Parallel Computing November 9 - 12, 2003 at Hohenwart Forum, Germany GAMM Fachausschuss Scientific Computing IfI/IWR Universitaet Heidelberg Technische Simulation STZ Technische Simulation WiR Baden-Wuerttemberg Organizers R.E. Bank, San Diego P. Bastian, Heidelberg H. C. Edwards, Albuquerque G. Wittum, Heidelberg Invited Speakers (tentative) H. C. Edwards, Albuquerque J. Fuhrmann, Berlin M. Holst, San Diego K. Kopps, Albuquerque S. Lang, Heidelberg Z. Mo, Beijing M. Parashar, Rutgers/Austin V. Reichenberger, Heidelberg J.-F. Remacle, Troy E. Stein, Hannover C. Wieners, Erlangen Topics Adaptivity Parallelism Computational Methods Software Tools Simulation of Application Problemson Adaptivity and Parallelism Simulation in science and technology is characterized by increasing model complexity and studies of full problem configurations. These trends result in high demands of computational resources. Thus advanced computational methods are necessary to overcome shortcomings. This workshop focuses on simulation tools using adaptivity and parallelism in the context of application problems and will bring together scientists of research and industry to discuss the state-of-the-art in area of simulation techniques and software tools. Registration Please find a registration form as pdf-file for download at http://www.wir-bawue.de, topic veranstaltungen. Address of registration office below. Submission of abstracts Please send your abstract (max 20 lines) by September 10, 2003. Notice of acceptance will be given as soon as possible. All participants, whether giving a talk or not, have the possibility of sending an abstract of their work on the topic of the conference. A collection of abstracts will be available during the conference. Deadlines Submission of abstracts September, 10th 2003 Registration September, 30th 2003 Payment September, 30th 2003 Conference Fee The conference fee for registration up to September, 30th 2003 is 350,- EUR including lodging and full board during the conferen ce, admission to all lectures and conference material. Financial support is available on request. For later registration we charge an additional fee of 100 EUR per person Payments are to be made in EURO by bank transfer: STZ Technische Simulation reference "workshop apc" Deutsche Bank, Heidelberg Bank code 672 700 03 Account nr 0153 114 Registration Office IWR -Technical Simulati Im Neuenheimer Feld 368 D- 69120 Heidelberg phone: ++49 (0) 6221 54 88 -66 or -54 fax: ++49 (0) 6221 54 88 60 Email: conference@wir-bawue.de The conference will be announced at http://www.wir-bawue.de Conference Venue Hohenwart Forum Conference Center Schoenbornstr. 25 75181 Pforzheim - Hohenwart phone ++49 (0) 7234 606 0 fax ++49 (0) 7234 606 46 You will reach Hohenwart by car, if you take Motorway A8 to the exit Pforzheim Ost. Follow the signposts to Calw. When you leave Pforzheim southbound, you will see the restaurant Kupferhammer on the left hand side. After hundred meters you take the next turn left and go up the hill to Huchenfeld and Hohenwart. When you enter Hohenwart, turn left behind the cemetery, then left again and you are at Hohenwart Forum. If you arrive at one of the airports, you take the train to Pforzheim, leave the station and walk to busstop Busbahnhof Sued (100m). The bus connecting Pforzheim with Hohenwart has number 742 (travel-agency Schuhmacher). You will recieve a timetable for the trains and busses after you have registered. A taxi from Pforzheim station to Hohenwart will cost 20 EUR. ------------------------------------------------------- Date: Sun, 31 Aub 2003 10:22:21 -0400 From: Craig Douglas Subject: Postdoctoral Position at University of Kentucky I have an immediate opening for a postdoctoral fellow as part of a new NSF funded project on dynamic data-driven application simulation (DDDAS) for wildland fire modeling. This is joint project with well known researchers at the University of Colorado-Denver, National Center for Atmospheric Research, Rochester Institute of Technology, and Texas A&M. Funding is expected for up to four years. The successful candidate must have 1) a Ph.D. in a relevant field (computer science preferred) 2) sound computational science experience 3) working knowledge of Fortran and C++ 4) parallel or Grid computing experience Please send a CV (pdf or Word formats) and cover material by email to me at craig.douglas@uky.edu with "DDDAS Postdoc Position" in the subject line. The University of Kentucky is an equal opportunity/affirmative action employer, and especially encourages applications from women and minorities. ------------------------------ End of MGNet Digest **************************