Send mail to: mgnet@cs.yale.edu for the digests mgnet-requests@cs.yale.edu for comments or help Anonymous ftp repository: casper.cs.yale.edu (128.36.12.1) World Wide Web: http://na.cs.yale.edu/mgnet/www/mgnet.html or Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) Volume 6, Number 2 (approximately February 29, 1996) Today's topics: Fredholm integral equation of the first kind inquiry Parallel/multigrid algorithms papers web site Quantum Chemistry Multigrid Web Site Some interesting web sites Preprint available (Jun Zhang) Preprint available (Zhangxin Chen) Preprint from Henson, Limber, McCormick, and Robinson Workshop on Iterative Methods (ILAY, CERFACS -- June 10-13, 1996) Call for Registration (AMLI'96, Nijmegen -- June 13-15, 1996) 1996 Copper Mountain Conference on Iterative Methods New Address (Lots of Jobs at NERSC in Berekeley, California) ------------------------------------------------------- Date: Fri, 9 Feb 96 11:55:02 PST From: Eldad Haber Subject: Fredholm integral equation of the first kind inquiry My name is Eldad and I'm a Ph.D student in geophysics in the University of British Columbia. I'm trying to solve a Fredholm integral equation of the first kind via multigrid. Could you refer me to a paper or a person which can help me. Thanks Eldad Editor's Note: If you want to help him, please contact him directly. ------------- ------------------------------------------------------- Date: Mon, 5 Feb 1996 18:18:00 -0600 From: Suely Oliveira Subject: Parallel/multigrid algorithms papers web site http://www.cs.tamu.edu/faculty/oliveira/ ------------------------------------------------------- Date: Wed, 14 Feb 1996 15:48:58 -0800 (PST) From: "Scott B. Baden" Subject: Quantum Chemistry Multigrid Web Site We've done some work with adaptive multigrid for quantum chemistry. Please direct readers to the following web site: http://www-cse.ucsd.edu/users/baden/samr.html ------------------------------------------------------- Date: Thu, 29 Feb 1996 14:26:19 -0500 (EST) From: Craig Douglas Subject: Some interesting web sites In the last issue, I inquired about interesting multigrid or domain decomposition web sites. Here are some of the ones that either I have found since then or been pointed to. I am going to pointers to these in the MGNet web pages (along with ones published earlier). Technical University of Chemnitz http://www.tu-chemnitz.de/~pester/sfb/spc.html CWI http://www.cwi.nl/cwi/departments/NW.html Hackbusch (German and English): http://www.informatik.uni-kiel.de/~jb/wh.html http://www.informatik.uni-kiel.de/~jb/wh.engl.html GMD (St. Augustin) http://www.gmd.de/GMD/Institutes/SCAI/scai_home.html ICASE http://www.icase.edu Konrad-Zuse-Zentrum Berlin http://www.zib-berlin.de/Numerik/ Joe Pasciak http://msg.das.bnl.gov/pasciak/ Van Henson http://math.nps.navy.mil/~vhenson/ Jinchao Xu http://www.math.psu.edu/xu/ If you want your page listed, send me the URL. ------------------------------------------------------- From: Jun Zhang Date: Mon, 26 Feb 1996 11:14:28 -0500 Subject: Preprint available (Jun Zhang) Analysis of Minimal Residual Smoothing in Multigrid JUN ZHANG Department of Mathematics The George Washington University, Washington, DC 20052, USA email: zhang@math.gwu.edu February 16, 1996 ABSTRACT We analyze the multigrid method accelerated by a minimal residual smoothing (MRS) technique. We prove that the MRS acceleration scheme is a semi-iterative method with respect to the original multigrid method and that the MRS accelerated multigrid method is a polynomial acceleration of first order. We explain the situations that MRS acceleration rate may slow down. The iteration matrices for the MRS accelerated coarse-grid-correction operator and the MRS accelerated two-level operator are obtained. In a simplified model, we give conditions for accelerating two-level method and some estimates for the acceleration rate. These analytical estimates agree quite well with our numerical results reported in an early paper: Minimal Residual Smoothing in Multi-level Iterative Method. The discussions in this paper are theoretical and are focused on the two-level method because MRS is only applied on the finest level of the multigrid method. Key words: Minimal residual smoothing, multigrid method, residual transfer, conjugate gradient-type methods. AMS subject classifications: 65F10, 65N06. Editor's Note: in mgnet/papers/Zhang/mrs-ana.ps.gz and .../mrs-ana.abs. ------------- ------------------------------------------------------- Date: Thu, 29 Feb 1996 10:12:02 -0600 From: Zhang-xin CHEN Subject: Preprint available (Zhangxin Chen) MULTIGRID AND MULTILEVEL METHODS FOR NONCONFORMING ROTATED Q1 ELEMENTS ZHANGXIN CHEN Department of Mathematics, Box 156 Southern Methodist University Dallas, Texas 75275--0156 PETER OSWALD Department of Mathematics Texas A&M University College Station, Texas 77843--3368 Abstract. In this paper we systematically study multigrid algorithms and multilevel preconditioners for discretizations of second-order elliptic problems using nonconforming rotated Q_1 finite elements. We first derive optimal results for the W-cycle and variable V-cycle multigrid algorithms; we prove that the W-cycle algorithm with a sufficiently large number of smoothing steps converges in the energy norm at a rate which is independent of grid number levels, and that the variable V-cycle algorithm provides a preconditioner with a condition number which is bounded independently of the number of grid levels. In the case of constant coefficients, the optimal convergence property of the W-cycle algorithm is shown with any number of smoothing steps. Then we obtain suboptimal results for multilevel additive and multiplicative Schwarz methods and their related V-cycle multigrid algorithms; we show that these methods generate preconditioners with a condition number which can be bounded at least by the number of grid levels. Also, we consider the problem of switching the present discretizations to spectrally equivalent discretizations for which optimal preconditioners already exist. Finally, the numerical experiments carried out here complement these theories. This paper is in the series of ISC-95-10-Math Technical Reports, Texas A&M University. It is available on http://www.isc.tamu.edu Editor's Note: in mgnet/papers/ChenZ-et-al/rotq1B.ps.gz and .../rotq1B.abs ------------- ------------------------------------------------------- Date: Fri, 1 Mar 96 12:56:26 PST From: vhenson@nps.navy.mil (Van Emden Henson) Subject: Preprint from Henson, Limber, McCormick, and Robinson Multilevel Image Reconstruction with Natural Pixels Van Emden Henson (1) Mark A. Limber (2) Stephen F. McCormick (3) Bruce T. Robinson (4) Abstract The sampled Radon transform of a 2D function can be represented as a continuous linear map A:L_2(W)--> R^N, where (Au)_j = < u, p_j> and p_j is the characteristic function of a strip through W approximating the set of line integrals in the sample. The image reconstruction problem is: given a vector b in R^N, find an image (or density function) u(x,y) such that Au=b. In general there are infinitely many solutions; we seek the solution with minimal 2-norm, which leads to a matrix equation $Bw = b, where B is a square dense matrix with several convenient properties. We analyze the use of Gauss-Seidel iteration applied to the problem, observing that while the iteration formally converges, there exists a near null space into which the error vectors migrate, after which the iteration stalls. The null space and near null space of B are characterized in order to develop a multilevel scheme. Based on the principles of the Multilevel Projection Method (PML), this scheme leads to somewhat improved performance. Its primary utility, however, is that it facilitates the development of a PML-based method for spotlight tomography, that is, local grid refinement over a portion of the image in which features of interest can be resolved at finer scale than is possible globally. (1) Department of Mathematics Naval Postgraduate School email: vhenson@nps.navy.mil (2) Auto-trol Technology Corporation, Denver, CO. email: marlim@Auto-trol.COM (3) Program in Applied Mathematics University of Colorado email: stevem@newton.colorado.edu (4) Accurate Information Systems Eatontown, NJ. email: brobinso@Accurate.COM Editor's Note: in mgnet/papers/Henson-Limber-McCormick-Robinson/image.ps.gz ------------- and .../image.abs ------------------------------------------------------- Date: Fri, 1 Mar 1996 18:56:34 -0700 From: pvanek@tiger.cudenver.edu (Petr Vanek) I just downloaded my amg code to mgnet/incoming. Sincerely yours Petr Vanek Editor's Note: now in mgnet/Codes/vanek/amg_code.tgz ------------- Algebraic multigrid solver based on smoothed aggregation. Fully automatic coarsening, capable of solving structural mechanics problems. Reliable if model consists of solids and plate; some problems with convergence may occur in the case of very thin and curved shells. Fortran-77 code. Petr Vanek: pvanek@tiger.cudenver.edu This is public domain software. ------------------------------------------------------- Date: Thu, 29 Feb 1996 14:26:19 -0500 (EST) From: Craig Douglas Subject: Workshop on Iterative Methods (ILAY, CERFACS -- June 10-13, 1996) CERFACS International Linear Algebra Year WORKSHOP ON ITERATIVE METHODS June 10-13, 1996 Programme This provisional programme is updated as soon as we receive final confirmation of the speaker(s). The invited speakers whose final confirmation we hope or expect to receive soon, are listed right after the programme. Click the (underlined) title to download the abstract of the talk. Monday June 10 : Industrial Day * F. Lafon (Thomson-CSF, France), Parallel methods for solving large electromagnetic problems on cluster of workstations. * P. W. Hemker (CWI, the Netherlands), Navier-Stokes and semiconductor modelling: two applications of adaptive non-linear Finite Volume Multigrid. A survey. * P. Markowitz (University of Berlin, Germany) * G. Meurant (CEA, France) * F.X. Roux (ONERA, France) Tuesday June 11 : Krylov Methods * S. Ashby (LLNL, USA) * T. Chan (UCLA, USA) * H. A. van der Vorst (Utrecht University, the Netherlands), Hybrid Iteration Methods. * A. Greenbaum (NYU, USA) Some Uses of the Symmetric Lanczos Algorithm -- and Why it Works!. * G. Golub (Stanford University, USA) * M. Heroux (Cray Research, USA), A Survey of Sparse BLAS Efforts. * T. Manteuffel (University of Colorado, USA) * D. Silvester (UMIST, UK) * R. Tuminaro (Sandia National Lab., USA) * A. Wathen (Oxford University, UK), Minimum Residual Methods for Augmented Systems Wednesday June 12 : Domain Decomposition Methods * J. Douglas (Purdue University, USA), Domain Decomposition Methods in Porous Medium Simulation. * D. E. Keyes (Old Dominion University and NASA Langley Research Center, USA), Multi-domain and Multi-model Aspects of Newton-Krylov-Schwarz Methods. * Y. Kuznetsov (Russian Academy of Sciences, Russia) * P. Le Tallec (INRIA, France), Generalised Neumann Preconditioners in Iterative Substructuring. * Y. Maday (Paris VI, France) * J. Mandel (University of Colorado, Denver, USA) * A. Quarteroni (Politecnico di Milano and CRS4, Italy), Iterative Domain Decomposition Methods for convection dominated problems. Thursday June 13 : Multigrid Methods * C. Douglas (IBM T.J. Watson Research Center and Yale University, USA), Multigrid on Unstructured Grids Using an Auxiliary Set of Structured Grids. * S. Brenner (University of South Carolina, USA), Multigrid Methods for Stress Intensity Factors. * P. Deuflhard (ZIB, Germany), The cascade principle and cascadic multigrid methods. * H. Elman (University of Maryland, USA) * U. Ruede (Technische Universitaet, Muenchen, Germany), Parallel Multilevel Adaptive Iteration. Other invited speakers who have not yet fully confirmed M. Arioli (CNR-Pavia), W. Hackbusch (Kiel), J. Periaux (Dassault). Local organizing committee Craig Douglas (IBM T.J. Watson Research Center and Yale University), Luc Giraud (CERFACS). Call for contribution A limited number of short talks presented in a circus session and posters will be selected for the workshop. THE DEADLINE FOR SUBMISSIONS IS MARCH 31, 1996. All submissions should include a title, together with a one to two page abstract, and should be sent to the ILAY Secretariat (email: wlay@cerfacs.fr). Location The workshop Iterative Methods will take place at the UNESCO Centre in Toulouse. Registration fees * Academic : 1500 FF (1700 FF)* * Student : 1000 FF (1200 FF)* (upon justification) * Non academic : 3000 FF (3500 FF)* *) for registration after April 30, 1996. The registration fees include the cost of the collection of the abstracts, lunches and coffee breaks. Accommodation On-site accommodation at the conference centre is available. The price is 174 FF for a single room and 112 FF per night and per person for a double room. Reservations are processed directly by the UNESCO Centre. How to register CERFACS is in charge of the registration for the workshops. Please proceed in two steps: 1) Registration for the workshop : Please print the registration form and return it to the following address ILAY Secretariat CERFACS Parallel Algorithms Project 42 Avenue Gustave Coriolis 31057 Toulouse CEDEX France Fax : (+33) 61-19-30-00 Email : rault@cerfacs.fr 2) Accommodation : Please download the accommodation form and return it, before April 30, 1996, to the UNESCO Centre that is in charge of the room reservations. The address is: Centre pour l'UNESCO, 4 place Agapito Nadal, BP. 3156, 31027 Toulouse France Phone : (+33) 62-13-62-13 Fax : (+33) 62-13-62-14 When booking, please indicate ``International Linear Algebra Year, Workshop on Iterative Methods''. Banquet A special dinner will be organized in Toulouse in the week of the workshop. Registration and payment for this dinner will take place at the conference, price : 150FF. For more information about the workshop, please contact the ILAY Secretariat. ------------------------------------------------------- Date: Thu, 29 Feb 1996 17:42:29 +0100 From: Maya Neytcheva Subject: Call for Registration (AMLI'96, Nijmegen -- June 13-15, 1996) ALGEBRAIC MULTILEVEL ITERATION METHODS WITH APPLICATIONS June 13-15, 1996 University of Nijmegen, The Netherlands SCOPE: The purpose of the conference is to provide a forum for the presentation and the discussion of recent progress in the analysis, implementation and applications in various fields of algebraic multilevel iteration methods in a broad sense. This includes their implementation on massively parallel computers. Topics covered include Algebraic Multilevel Iteration methods for - second and fourth order elliptic scalar equations and systems of equations, - mixed variable variational problems - nonselfadjoint problems and indefinite matrix problems - inner-outer iteration methods - parallel implementations, efficiency measures, scalability - robust implementations, - applications for Navier's equations and Stokes problem - applications outside partial differential equation problems - applications for nonlinear problems (electromagnetic field, plastic flow, Navier-Stokes, and Miscible displacement problems, etc). INVITED SPEAKERS: Dietrich Braess, Bochum, Germany James Bramble, College Station, USA Tony Chan, Los Angeles, USA Richard Ewing, College Station, USA Karl Gustafson, Boulder, USA Wolfgang Hackbusch, Kiel, Germany Yuri Kuznetsov, Moscow, Russia Jean-Francois Maitre, Lyon, France Panayot Vassilevski, Sofia, Bulgaria Harry Yserentant, Tubingen, Germany SPONSORS: Stichting Mathematisch Centrum (SMC), Amsterdam Mathematics Research Institute (MRI), The Netherlands DEADLINES: April 16, 1996 Submission of extended abstracts May 1, 1996 Final program with notification of acceptance REGISTRATION FEES: Before April 14 Before May 16 On site DFL 450 DFL 500 DFL 600 For students DFL 250 DFL 300 DFL 400 The students must show a paper certifying their status. The registration fee has to be transferred to: Generale Bank, Nijmegen Bank account: 23.12.47.834 att. Catholic University Nijmegen Faculty of Mathematics and Informatics Nijmegen, with reference to FW1184 postgiro of the bank: 1775387 PRELIMINARY INFORMATION FOR HOTEL RESERVATION: Category Single room (DFL) Double room (DFL) A 160 - 190 180 - 230 B 70 - 95 110 - 160 C 33 66 NOTE: The rooms available in category C are limited and the prices are without breakfast, which costs extra DFL 13 per person. TO GET THE APPLICATION FORM PLEASE CONTACT: AMLI'96, Faculty of Mathematics and Informatics Toernooiveld 1, NL-6525 ED Nijmegen, The Netherlands e-mail: amli96@sci.kun.nl fax: +31 (0)24 3652140 ------------------------------------------------------- From: Steve Mccormick Date: Mon, 12 Feb 1996 09:01:55 -0700 Subject: 1996 Copper Mountain Conference on Iterative Methods Rooms for this year's Copper Mountain Conference on Iterative Methods are going fast. In fact, Copper was full until they released about 10 one- and two-bedrooms on February 10th. But they will no doubt go fast. If you plan to attend but do not yet have a room, you should call Copper Mountain immediately. Other rooms might be available from the following management companies at Copper: Carbonate (800) 458-8386 CMCR (800) 526-7737 High Country Vacations (800) 426-7400 For further information, please access our Web site at http://amath-www.colorado.edu/appm/faculty/ccmm/cmcim96.html Steve McCormick: Appl. Math, C.B. 526, U. of CO, Boulder, CO 80309-0526 (303)492-0662 stevem@newton.colorado.edu ftp://amath.colorado.edu/pub -4066fax http://amath-www.colorado.edu/appm/faculty/stevem/Home.html ------------------------------------------------------- Date: Fri, 9 Feb 1996 07:34:32 -0800 From: "Horst Simon" Subject: New Address I have accepted a new position at Lawrence Berkeley National Laboratory as director of the NERSC Division. As you may have heard, DoE has decided to relocate the NERSC supercomputer center from Livermore to Berkeley. This decision is documented in http://www.nersc.gov/doc/Whats_New/decisiondoc.html and general information about NERSC can be found http://www.nersc.gov NERSC will run in the near future a 512 processor T3E as well as a cluster of J90 machines and move the Cray C90 from Livermore to Berkeley. I am very excited to be in the middle of the re-creation of a supercomputer center. In particular I am looking forward to the increased interaction with the UC Berkeley computer science and applications community. There are many job openings at NERSC, they are listed at http://ux9.lbl.gov/LBL-Documents/CJOs/ Please bring them to the attention of interested students and others. Horst D. Simon Director, NERSC Division Lawrence Berkeley National Laboratory Mail Stop 50A/5104 University of California Berkeley, CA 94720 (510) 486-7377 (510) 486-6060 simon@nersc.gov ------------------------------ End of MGNet Digest **************************