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@cs.yale.edu) Volume 8, Number 5 (approximately May 31, 1998) Today's topics: Important dates Using Mutigrid from Numerical Recipes Staff Positions at LANL New preprints available (D. Arnold et al) Copper Mountain 98 Paper by Bermejo and Infante Copper Mountain 98 Paper by Lackner and Menikoff Some of the new entries in the bibliography ------------------------------------------------------- Date: Sun, 31 May 1998 12:31:11 -0500 From: Craig Douglas Subject: Important dates June 15 The date changed for abstracts for the 10th Anniversary International GAMM - Workshop on Multigrid Methods, October 5 - 8, 1998 at Bonn (Germany). See http://wwwwissrech.iam.uni-bonn.de/mg10. July 20 The absolute deadline for registration for the 11th International Conference on Domain Decomposition Methods. See http://dd11.gre.ac.uk. ------------------------------------------------------- Date: Wed, 3 Jun 1998 10:20:22 -0500 From: "Mainkar, Neeraj" Subject: Using Mutigrid from Numerical Recipes I have been struggling with trying to understand how to use the MultiGrid Algorithm from Numerical Recipes to tailor it to my problem. I have a 3D problem and the domain is NOT a simple box. Isn't there a program out there which I could use for 3D and has a separate module to specify the geometry and the boundary conditions of the problem? Any help would immensely appreciated. Desperately seeking help Neeraj Mainkar Simulations Modeler Editor's Note: Clearly UG, Kaskade, and FE++ should work (links can be ------------- found on the codes web page for UG and Kaskade and in the links web page for FE++). However, this is an opportunity for people with new codes to volunteer information to Mainker. Please cc MGNet. ------------------------------------------------------- Date: Mon, 18 May 1998 10:30:43 -0600 (MDT) From: Michele Benzi Subject: Staff Positions at LANL Technical Staff Member Positions Los Alamos National Laboratory (PARALLEL COMPUTATION AND SPARSE LINEAR ALGEBRA) The Scientific Computing Group of Los Alamos National Laboratory is currently seeking highly qualified researchers in parallel computing and sparse linear algebra to participate in an interdisciplinary research and development effort in high performance computing for large-scale physical modeling and simulation problems. Researchers with experience in the following categories are encouraged to apply: Parallel Computer Programming Numerical Linear Algebra Software Library Development Parallel Applications Development Iterative Linear Solver Methods Parallel Preconditioning Techniques Geometric and Algebraic Multigrid Methods Participants will assist in developing innovative algorithms and codes in conjunction with LANL/DOE projects such as ASCI as well as industrial collaborations seeking to perform multibillion gridcell computations on parallel platforms of up to 100 Tflops and beyond. Expertise and experience in iterative linear solution techniques such as generalized conjugate gradient methods, preconditioning techniques such as incomplete LU preconditioning, domain decomposition methods, and geometric and/or algebraic multigrid and multilevel methods is desirable. Professional-level experience in programming and software development on parallel computers using message passing and Fortran 90 or C is desirable. A Ph.D. in applied mathematics, computer science or related technical field, or equivalent combination of technical degree(s) and experience is required. A "Q" clearance or ability to obtain one is highly desirable. Technical staff positions at Los Alamos National Laboratory offer competitive salaries and a generous benefits package. Team members have access to world-class computing facilities and are granted a substantial travel budget. Further information about currently available positions may be found at http://www.hr.lanl.gov/scripts/jobs/Single.idc?ReqNumber=983107 Information regarding the technical content of these efforts can be found at the Parallel Architectures and Algorithms Team web site http://www.c3.lanl.gov/cic19/teams/par_arch/par_arch.shtml Instructions on how to apply for these positions may be found at http://www.hr.lanl.gov/html/jobs/apply_external.html Individuals interested in obtaining further information on these positions may contact Michele Benzi for further information: Michele Benzi Los Alamos National Laboratory Group CIC-19, MS B-256 Los Alamos, NM 87545 EMAIL: benzi@lanl.gov Los Alamos National Laboratory, a world-class multidisciplinary research facility, is engaged in state-of-the-art research in areas such as advanced computing, computer simulation and computer modeling, sensors and instrumentation for complex experimentation and measurements, nuclear weapons, earth and environmental science, bioscience and biotechnology, materials science, and nuclear science, plasmas, and beams. Los Alamos is located between the majestic Sangre de Cristo and Jemez mountain ranges of northern New Mexico and is near the cultural and resort centers of Santa Fe and Taos, NM. Los Alamos is an equal-opportunity employer. ------------------------------------------------------- Date: Wed, 13 May 1998 12:29:27 -0400 From: "Douglas N. Arnold" Subject: New preprints available (D. Arnold et al) Dear Colleagues: This note is to let you know of four recent preprints that have been added to my Web page and which may be of interest to you. These are listed below, first titles only, and then full bibliographic information. You can view or download these papers at http://www.math.psu.edu/dna/publications.html, or retrieve them by anonymous ftp at ftp.math.psu.edu, directory pub/dna/papers. These bring to 32 the number of my papers available online. If you would prefer that I mail you a hardcopy of one or more of these, just let me know. Regards -- Doug New titles as of 5/98: Multigrid preconditioning in H(div) on non-convex polygons Locally adapted tetrahedral meshes using bisection Adaptive finite elements and colliding black holes Multigrid in H(div) and H(curl) ==> hdivn-info.txt <== Title: Multigrid preconditioning in H(div) on non-convex polygons Authors: Douglas N. Arnold, Richard S. Falk, and Ragnar Winther Source: Computational and Applied Mathematics Status: To appear Abstract: In an earlier paper we constructed and analyzed a multigrid preconditioner for the system of linear algebraic equations arising from the finite element discretization of boundary value problems associated to the differential operator I - grad div. In this paper we analyze the procedure without assuming that the underlying domain is convex and show that, also in this case, the preconditioner is spectrally equivalent to the inverse of the discrete operator. Keywords: preconditioner, finite element, multigrid, nonconvex domain Subj. class.: 65N55, 65N30 FTP site: ftp.math.psu.edu File name: pub/dna/papers/hdivn.dvi File format: TeX DVI file File name: pub/dna/papers/hdivn.ps File format: PostScript file ==> bistet-info.txt <== Title: Locally adapted tetrahedral meshes using bisection Authors: Douglas N. Arnold, Arup Mukherjee, and Luc Pouly Source: SIAM Journal on Scientific Computing Status: Submitted Abstract: We present an algorithm for the construction of locally adapted conformal tetrahedral meshes. The algorithm is based on bisection of tetrahedra. A new data structure is introduced, which simplifies both the selection of the refinement edge of a tetrahedron and the recursive refinement to conformity of a mesh once some tetrahedra have been bisected. We prove that repeated application of the algorithm leads to only finitely many tetrahedral shapes up to similarity, and bound the amount of additional refinement that is needed to achieve conformity. Numerical examples of the effectiveness of the algorithm are presented. Keywords: bisection, tetrahedral meshes, adaptive refinement, similarity classes, finite elements Subj. class.: 65N50 FTP site: ftp.math.psu.edu File name: pub/dna/papers/bistet.dvi File format: TeX DVI file File name: pub/dna/papers/bistet.ps File format: PostScript file Note: PostScript version contains figures ==> hdivcurl-info.txt <== Title: Multigrid in H(div) and H(curl) Authors: Douglas N. Arnold, Richard S. Falk, and Ragnar Winther Source: Numerische Mathematik Status: Submitted Abstract: We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces H(div) and H(curl) in three dimensions. We show that if appropriate finite element spaces and appropriate additive or multiplicative Schwarz smoothers are used, then the multigrid V-cycle is an efficient solver and preconditioner for the discrete operator. All results are uniform with respect to the mesh size, the number of mesh levels, and weights on the two terms in the inner products. Keywords: multigrid, preconditioner, mixed method, finite element Subj. class.: 65N55, 65N30 FTP site: ftp.math.psu.edu File name: pub/dna/papers/hdivcurl.dvi File format: TeX DVI file File name: pub/dna/papers/hdivcurl.ps File format: PostScript file ==> dundee-info.txt <== Title: Adaptive finite elements and colliding black holes Authors: Douglas N. Arnold, Arup Mukherjee, and Luc Pouly Source: Numerical Analysis 1997: Proceedings of the 17th Biennial Conference on Numerical Analysis Status: To appear Abstract: According to the theory of general relativity, the relative acceleration of masses generates gravitational radiation. Although gravitational radiation has not yet been detected, it is believed that extremely violent cosmic events, such as the collision of black holes, should generate gravity waves of sufficient amplitude to detect on earth. The massive Laser Interferometer Gravitational-Wave Observatory, or LIGO, is now being constructed to detect gravity waves. Consequently there is great interest in the computer simulation of black hole collisions and similar events, based on the numerical solution of the Einstein field equations. In this note we introduce the scientific, mathematical, and computational problems and discuss the development of a computer code to solve the initial data problem for colliding black holes, a nonlinear elliptic boundary value problem posed in an unbounded three dimensional domain which is a key step in solving the full field equations. The code is based on finite elements, adaptive meshes, and a multigrid solution process. Here we will particularly emphasize the mathematical and algorithmic issues arising in the generation of adaptive tetrahedral meshes. Keywords: adaptivity, finite elements, black holes, Einstein equations Subj. class.: 65N50, 65N30, 83C05, 83C35, 83C57 FTP site: ftp.math.psu.edu File name: pub/dna/papers/dundee.dvi File format: TeX DVI file File name: pub/dna/papers/bistet.ps File format: PostScript file Note: PostScript version contains figures ------------------------------------------------------- Date: Wed, 20 May 98 16:27:45 +0200 From: infante@sunma4.mat.ucm.es (Juan Antonio Infante) Subject: Copper Mountain 98 Paper by Bermejo and Infante This is to inform you that we put an abstract and a ps-file of our Copper Mountain 98 paper into the directory /incoming/bermejo at ftp www.mgnet.org. The paper is definite version of the extended abstract of the Copper Mountain Proceedings. Thank you very much, R.Bermejo and J.A. Infante A Multigrid Algorithm for Nonlinear Monotone Elliptic Problems R. Bermejo and J.A. Infante We introduce a FAS multigrid algorithm to find the finite element solution for a class of nonlinear monotone elliptic problems. Since the solution of the problem is equivalent to minimize a strictly convex functional, we use Polak-Ribiere conjugate gradient method as the nonlinear smoother in our algorithm. The advantage in so doing is that we do not have to calculate derivatives of operators. We prove the convergence of our algorithm and illustrate its performance by solving benchmark problems. Editor's Note: in www.mgnet.org/mgnet-cmcim98.html or you can directly ------------- access it in mgnet/Conferences/CMCIM98/bermejo.ps.gz ------------------------------------------------------- Date: Fri, 22 May 1998 10:10:23 -0500 Subject: Copper Mountain 98 Paper by Lackner and Menikoff Multi-Scale Linear Solvers for Very Large Systems Derived from PDEs Klaus Lackner (ksl@lanl.gov) Theoretical Division, Mail Stop B-216, Los Alamos National Laboratory, Los Alamos, NM 87544 Ralph Menikoff (rtm@lanl.gov) Theoretical Division, Mail Stop B-214, Los Alamos National Laboratory, Los Alamos, NM 87544 ABSTRACT We present a novel linear solver that works well for large systems obtained from discretizing PDEs. It is robust and, for the examples we studied, the computational effort scales linearly with the number of equations. The algorithm is based on a wavelength decomposition that combines conjugate gradient, multi-scaling and iterative splitting methods into a single approach. On the surface, the algorithm is a simple preconditioned conjugate gradient with all the sophistication of the algorithm in the choice of the preconditioning matrix. The preconditioner is a very good approximate inverse of the linear operator. It is constructed from the inverse of the coarse grained linear operator and from smoothing operators that are based on an operator splitting on the fine grid. The coarse graining captures the long wavelength behavior of the inverse operator while the smoothing operator captures the short wavelength behavior. The conjugate gradient iteration accounts for the coupling between long and short wavelengths. The coarse grained operator corresponds to a lower resolution approximation to the PDEs. While the coarse grained inverse is not known explicitly, the algorithm only requires that the preconditioner can be a applied to a vector. The coarse inverse applied to a vector can be obtained as the solution of another preconditioned conjugate gradient solver that applies the same algorithm to the smaller problem. Thus, the method is naturally recursive. The recursion ends when the matrix is sufficiently small for a solution to be obtained efficiently with a standard solver. The local feedback provided by the conjugate gradient step at every level makes the algorithm very robust. In spite of the effort required for the coarse inverse, the algorithm is efficient because the increased quality of the approximate inverse greatly reduces the number of times the preconditioner needs to be evaluated. A feature of the algorithm is that the transition between coarse grids is determined dynamically by the accuracy requirement of the conjugate gradient solver at each level. Typically, later iterations on the finer scales need fewer iterations on the coarser scales and the computational effort is proportional to N rather than NlogN, where N is the number of equations. We have tested our solver on the porous flow equation. On a workstation we have solved problems on grids ranging in dimension over 3 orders of magnitude, from 103 to 106, and found that the linear scaling holds. The algorithm works well, even when the permeability tensor has spatial variations exceeding a factor of 109. Editor's Note: in www.mgnet.org/mgnet-cmcim98.html or you can directly ------------- access it in mgnet/Conferences/CMCIM98/menikoff.ps.gz ------------------------------------------------------- Date: Sun, 31 May 1998 14:42:12 -0200 From: Craig Douglas Subject: Some of the new entries in the bibliography The latest version is dated June 4, 1998 and has 3240 entries. Here are some recent new entries. As usual, please send additions and corrections. REFERENCES [1] M. Arioli and C. Fassino, Roundoff error analysis of algo- rithms based on Krylov subspace methods, BIT, 36 (1996), pp. 189-205. [2] C. Ashcraft and J. W. H. Liu, Using domain decomposition to find graph bisectors., BIT, 37 (1997), pp. 506-534. [3] B. Bialecki and D. S. Dillery, Fourier analysis of Schwarz alternating methods for piecewise Hermite bicubic orthogo- nal spline collocation, BIT, 33 (1993), pp. 634-646. [4] S. C. Brenner and L. Y. Sung, Multigrid methods for the computation of singular solutions and stress intensity factors II. Crack singularities, BIT, 37 (1997), pp. 623-643. [5] C. Brezinski and M. Redivo Zaglia, Look-ahead in Bi- CGSTAB and other product-type methods for linear systems, BIT, 35 (1995), pp. 169-201. [6] A. M. Bruaset and A. Tveito, A numerical study of opti- mized sparse preconditioners, BIT, 34 (1994), pp. 177-204. [7] K. Burrage, Z. Jackiewicz, S. P. Norsett, and R. A. Renaut, Preconditioning waveform relaxation iterations for differential systems, BIT, 36 (1996), pp. 54-76. [8] S. L. Campbell, I. C. F. Ipsen, C. T. Kelley, and C. D. Meyer, GMRES and the minimizing polynomial, BIT, 36 (1996), pp. 664-675. [9] T. F. Chan, W. P. Tang, and W. L. Wan, Wavelet sparse approximate inverse preconditioners, BIT, 37 (1997), pp. 644-660. [10] C. Christara and B. F. Smith, Multigrid and multilevel methods for quadratic spline collocation, BIT, 37 (1997), pp. 781-803. [11] S. S. Clift and W.-P. Tang, Weighted graph based order- ing techniques for preconditioned conjugate gradient meth- ods, BIT, 35 (1995), pp. 30-47. [12] C. C. Douglas, S. Malhotra, and M. H. Schultz, A characterization of mapping unstructured grids onto struc- tured grids and using multigrid as a preconditioner, BIT, 37 (1997), pp. 661-677. [13] J. Douglas and C.-S. Huang, An accelerated domain decom- position procedure based on Robin transmission conditions, BIT, 37 (1997), pp. 678-686. [14] J. Drko~sov'a, A. Greenbaum, M. Rozlo~znik, and Z. Strako~s, Numerical stability of GMRES, BIT, 35 (1995), pp. 309-330. [15] M. Dryja and W. Hackbusch, On the nonlinear domain decomposition method, BIT, 37 (1997), pp. 296-311. [16] D. J. Evans and G.-Y. Lei, Approximate inverses of multi- diagonal matrices and application to the block PCG method, BIT, 35 (1995), pp. 48-63. [17] S. Farestam and R. B. Simpson, A framework for advancing front techniques of finite element mesh generation, BIT, 35 (1995). [18] J. L. Fattebert, An inverse iteration method using multigrid for quantum chemistry, BIT, 36 (1996), pp. 509-522. [19] A. Greenbaum, M. Rozlo~znik, and Z. Strako~s, Numerical behaviour of the modified Gram-Schmidt GMRES implemen- tation, BIT, 37 (1997), pp. 706-719. [20] I. Gustafsson, An incomplete factorization preconditioning method based on modification ofelement matrices, BIT, 36 (1996), pp. 86-100. [21] T. Huckle, Fast transforms for trdiagonal linear equations, BIT, 34 (1994), pp. 99-112. [22] H. Q. Jin, A note on best conditioned preconditioners, BIT, 34 (1994), pp. 312-317. [23] C. Lacour and Y. Maday, Two different approaches for matching nonconforming grids: the mortar element method and the FETI method, BIT, 37 (1997), pp. 720-738. [24] Z. Leyk, Breakdowns and stagnation in iterative methods., BIT, 37 (1997), pp. 377-403. [25] H. L"otzbeyer and U. R"ude, Patch-adaptive multilevel iter- ation, BIT, 37 (1997), pp. 739-758. [26] O. Nevanlinna, Convergence of Krylov methods for sums of two operators, BIT, 36 (1996), pp. 775-785. [27] Th. Rottner, L. Lenhardt, G. Alefeld, and K. Schweizerhof, Nonlinear structural finite element analysis using the preconditioned Lanczos method on serial and parallel computers, BIT, 37 (1997), pp. 759-769. [28] M. A. Saunders, Solution of sparse rectangular systems with LSQR and CRAIG, BIT, 35 (1995), pp. 586-602. [29] R. B. Simpson, A data base abstraction of describing triangular mesh algorithms, BIT, 37 (1997), pp. 138-163. [30] S. Ta'asan and H. Zhang, Fourier-Laplace analysis of the multigrid waveform relaxation method for hyperbolic equa- tions, BIT, 36 (1996), pp. 831-841. ------------------------------ End of MGNet Digest **************************