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: casper.cs.yale.edu (128.36.12.1) ftp.cerfacs.fr (138.63.200.33) World Wide Web: http://na.cs.yale.edu/mgnet/www/mgnet.html or http://www.cerfacs.fr/~douglas/mgnet.html Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) Volume 6, Number 7 (approximately July 31, 1996) Today's topics: Strobl Virtual Proceedings Triangle Mesh Generator Available Data structures for adaptive multilevel-FEM methods Updated Codes: UG version 3.3 and PLTMG version 7.2 1995 Copper Mountain Proceedings Some of the new entries in the bibliography ***************************************************************************** ***** August is traditionally a slow month. Please send contributions. ***** ***************************************************************************** ------------------------------------------------------- Date: Wed, 3 Jul 96 08:52:01 +0200 From ghaase@mephisto Wed Jul 3 03:18:36 1996 Subject: Strobl Virtual Proceedings Virtual Proceedings of the 9th International GAMM-Workshop on Parallel Multigrid Methods at http://www.numa.uni-linz.ac.at/Workshops/proceedings.html are available. Editor's Note: in mgnet/Conferences/ParMGM96 and the MGNet web page for ------------- this conference. Here is a list of what is there so far: Clemens Brand and Johannes Kraus: Preconditioning by Approximative Schur Complements on Hierarchical Grids Dietrich Braess: Towards Algebraic Muligrid for Elliptic Problems of Second Order. Michael Czajkowski : Application of Multigrid to an Initial Control Problem. Wolfgang Dahmen : Stable Multiscale Bases and Adaptive Techniques for Elliptic Problems. Craig Douglas : Caching in with Multigrid Algorithms: Problems in Two Dimensions. Jurgen Fuhrmann : A Modular Algebraic Multilevel Method. Csaba Gaspar: Flow modelling using quadtrees and multigrid technique. Klaus Gartner : Improved Separators by Multigrid Methods. Wolfgang Hackbusch : Downwind Gauss-Seidel Smoothing for Convection Dominated Problems. Volker John : Parallel Solution Schemes for the Navier-Stokes Equation using the Crouzeix/Raviart-Element. Michael Jung : Parallelization of multi-grid methods based on domain decomposition ideas. Michael Jung and Michael Thess : Parallel Multilevel Solvers for 3D Problems. Holger Matthes : Parallel preconditioners for plate and shell problems. Maya Neytcheva ,Owe Axelsson and Krassimir Georgiev : Algebraic Multilevel Iteration Method on massively parallel computer architectures. Ulrich Rude : Performance Aspects of Iterative Methods on Superscalar Computers. Barry Smith : Abstract Parallel Multigrid Software in PETSc 2.0. Ivan Sofronov : Jump-Keeping and Upwind Transfer in MultiGrid for Upwind Schemes. Rob Stevenson : A Robust Hierarchical Basis Preconditioner on General Meshes. Karsten Urban : A multiscale method for separation processes in chemnical engineering. Yuri Vassilevski, Yuri Iliash and Yuri Kuznetsov : Efficient Parallel Solving the Potential Flow Problem on Nonmatching Grids. Frank Wagner : Time-paralle Multigrid Methods for Two-Phase Stefan Problems. ------------------------------------------------------- From: Jonathan ShewchukDate: Sun, 21 Jul 96 21:24:43 EDT Subject: Triangle Mesh Generator Available Triangle Version 1.3 A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator. Triangle generates 2D Delaunay triangulations, Voronoi diagrams, convex hulls, constrained Delaunay triangulations, and quality conforming Delaunay triangulations. The latter can be generated with no small angles, and are thus suitable for finite element analysis. Triangle includes an implementation of Ruppert's Delaunay refinement algorithm for 2D meshing. Users can specify constraints on minimum angle and maximum triangle area, and can refine previously generated meshes based on a posteriori error estimates. Support is included for holes, concavities, internal boundaries, and intersecting segments. The Delaunay triangulations and constrained Delaunay triangulations produced are exact, but very little speed is sacrificed to gain this robustness. Hence, Triangle is useful not only for finite element practitioners, but also for computational geometers who seek a comparison to validate the robustness of their codes against. Triangle is accompanied by a simple X program called "Show Me", whose purpose is to display point sets, planar straight line graphs, triangulations, partitions, and Voronoi diagrams. It also creates PostScript output. Triangle is about 13,000 lines of portable C code, and Show Me about 3,400. Each is a single, easy-to-compile file. New features in Version 1.3: Faster file reading. Interface for calling Triangle from another program. Attributes that allow you to determine which (segment-bounded) region a triangle falls in. Triangle neighbor lists. Objects can be numbered from zero. Ability to suppress insertion of new points on the boundary, thus preserving compatibility with adjacent meshes. Handles duplicate input points correctly. Full online documentation for Triangle is available on the Web at http://www.cs.cmu.edu/~quake/triangle.html Jonathan Shewchuk School of Computer Science Carnegie Mellon University jrs@cs.cmu.edu Editor's Note: in mgnet/Codes/triangle. ------------- ------------------------------------------------------- From: Juergen Fuhrmann Date: Mon, 24 Jun 96 11:50:11 +0200 Subject: Data structures for adaptive multilevel-FEM methods The 1st Workshop "Data structures for adaptive multilevel-FEM methods" took place at the Weierstrass Institute for Applied Analysis and Stochastics (WIAS) in Berlin, on May 29.- 31.1996. It was initiated by R.Kornhuber (Univ. Stuttgart) and organized by J.Fuhrmann, H.Langmach (WIAS) and by R.Roitzsch, B.Erdmann, R.Beck (ZIB). The workshop has been divided into two parts: a "classical" talks section, where the participants had the possibility to present their approaches to the topic, and a discussion section, where three working groups discussed the following topics: * Efficiency of the implementation of adaptive algorithms * Programming in Scientific Computing (motivation and aims) * Software interfaces for finite element applications Detailed information you can find on the WWW page http://www.wias-berlin.de/~amfem. Because of some access problems, there is a mirror of this site at http://www.zib-berlin.de/~amfem. The topics of these discussions, and the topic of the workshop as a whole, are seldomly covered by events in scientific life, even though Scientific Computing would not exist without serious efforts in software development. The participants felt that it had been very useful to meet at this workshop and that it would be worth to try to continue the work of this meeting. For this purpose, a moderated mailing list amfem-l@zib-berlin.de has been installed. To subscribe the mailing list, send an e-mail to majordomo@zib-berlin.de with the body subscribe amfem-l The contributions to this mailing list are collected on http://elib.zib-berlin.de/amfem-l. Everyone interested in the topic of the workshop or who is concerned with programming and data structure issues for Scientific Computing, is invited to participate. Especially, submissions to the sparse matrix benchmark effort (see the summary of the discussion of the efficiency working group at the www-page) are welcome. In the hope of a fruitful discussion Juergen Fuhrmann Rainer Roitzsch ------------------------------------------------------- Date: Tue, 30 Jul 1996 12:12:12 GMT From: Craig Douglas Subject: Updated Codes: UG version 3.3 and PLTMG version 7.2 Two software packages on MGNet have been updated recently. The first is UG version 3.3, from Gabriel Wittum's institute at Stuttgart (thank you, Peter Bastian for this). The other is PLTMG version 7.2, from Randy Bank at the University of California at San Diego. Editor's Note: in mgnet/Codes/ug/ug3.3 and ------------- mgnet/Codes/pltmg. ------------------------------------------------------- Date: Mon, 29 Jul 1996 19:51:06 GMT From: Duane Melson Subject: 1995 Copper Mountain Proceedings Craig, They still have not been mailed out yet. I hate to give an estimate again because none of the rest of my estimates have worked out. If you would, please mention in the next digest that attendees of the conference should make sure that I have their current address so that I can mail out their copies as soon as they are available. Duane ------------------------------------------------------- Date: Mon, 29 Jul 1996 18:12:10 -0500 From: Craig Douglas Subject: Some of the new entries in the bibliography Randy Bank submitted his list of publications, some of which are included below. Here are some recent new entries. As usual, please send additions and corrections. The most recently posted bibliography is dated July 29, 1996. REFERENCES [1] B. Achchab and J. F. Maitre, Estimate of the constant in two strenghtened C.B.S. inequalities for the F.E.M. sys- tem of the 2D elasticity. application to multilevel methods and a posteriori error estimators, Numer. Lin. Alg. Appl., 3 (1996), pp. 147-159. [2] O. Axelsson, An algebraic framework for hierarchical basis function multilevel methods or the search for `optimal' pre- conditioners, in Iterative Methods for Large Linear Systems, Academic Press, New York, 1990, pp. 7-40. [3] ______, Iterative Solution Mehtods, Cambridge University Press, Cambridge, 1994. [4] ______, Stbilization of algebraic multilevel iteration; additive methods, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 1, Nijmegan, The Netherlands, 1996, University of Ni- jmegan, pp. 49-62. [5] O. Axelsson and M. Neytcheva, A survey of multilevel preconditioned iterative methods, Numer. Lin. Alg. Appl., 1 (1994), pp. 213-236. [6] ______, Scalable algorithms for the solution of Navier's equations of elasticity, J. Comp. Appl. Math., 63 (1995), pp. 149-178. [7] O. Axelsson and B. Polman, AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, University of Nijmegan, Nijmegan, The Netherlands, 1996. [8] O. Axelsson and P. S. Vassilevski, A survey of multilevel preconditioned iterative methods, BIT, 29 (1989), pp. 769- 793. [9] ______, Asymptotic work estimates for AMLI methods, Appl. Nu- mer. Math., 7 (1991), pp. 437-451. [10] Z.-Z. Bai, A class of hybrid algebraic multilevel preconditioning methods, Appl. Numer. Math., 19 (1996), pp. 389-399. [11] Z.-Z. Bai and O. Axelsson, A unified framework for the construction of various algebraic multilevel preconditioning methods, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 1, Nijmegan, The Netherlands, 1996, University of Ni- jmegan, pp. 63-76. [12] R. E. Bank, Marching Algorithms for Elliptic Boundary Value Problems, PhD thesis, Division of Engineering and Applied Physics, Harvard University, Cambridge, MA, 1975. [13] ______, A multi-level iterative method for nonlinear elliptic equa- tions, in Elliptic Problem Solvers, M. H. Schultz, ed., Aca- demic Press, New York, 1981, pp. 1-16. [14] ______, Efficient implementation of local mesh refinement algo- rithms, in Adaptive Computational Methods for Partial Dif- ferential Equations, I. Babu~ska, J. Chandra, and J. E. Fla- herty, eds., SIAM, Philadelphia, 1984, pp. 74-81. [15] ______, Analysis of a local a posteriori error estimator for elliptic equations, in Accuracy Estimates and Adaptivity in Finite Element Computations, J. Wiley & Sons, New York, 1986, pp. 119-128. [16] ______, Computational Aspects of VLSI Design with an Empha- sis on Semiconductor Device Simulation, vol. 25 of Lecture Notes in Applied Math., American Mathematical Society, Providence, 1990. [17] ______, Hierarchical preconditioners for elliptic partial differen- tial equations, in Large Scale Matrix Problems and the Nu- merical Solution of Partial Differential Equations, Oxford University Press, Oxford, UK, 1994, pp. 121-155. [18] ______, Hierarchical bases and the finite element method, vol. 5 of Acta Numerica, Cambridge University Press, Cambridge, 1996, pp. 1-43. [19] R. E. Bank, R. Bulirsch, H. Gajewski, and K. Merten, Mathematical Modelling and Simulation of Electrical Cir- cuits and Semiconductor Devices, vol. 117 of Int. Series Nu- mer. Math., Birkh"auser, Basel, 1994. [20] R. E. Bank, R. Bulirsch, and K. Merten, Mathematical Modelling and Simulation of Electrical Circuits and Semi- conductor Devices, vol. 93 of Int. Series Numer. Math., Birkh"auser, Basel, 1990. [21] R. E. Bank and H. D. Mittelmann, Stepsize selection in continuation procedures and damped Newton's method, J. Comp. and Appl. Math., 26 (1989), pp. 67-78. [22] R. E. Bank and R. F. Santos, Analysis of some moving space-time finite element methods, SIAM J. Numer. Anal., 30 (1993), pp. 1-18. [23] R. E. Bank, A. H. Sherman, and A. Weiser, On the regularity of local mesh refinement, in Proceedings of the IMACS Tenth World Conference, New Brunswick, NJ, 1982, IMACS. [24] R. E. Bank, B. D. Welfert, and H. Yserentant, A class of iterative methods for solving mixed finite element equa- tions, Numer. Math., 56 (1990), pp. 645-666. [25] R. E. Bank and J. Xu, A hierarchical basis multigrid method for unstructured grids, in Fast Solvers for Flow Problems. Proceedings of the Tenth GAMM-Seminar Kiel, vol. 49 of Notes on Numerical Mathematics, Vieweg-Verlag, Braun- schweig, 1995, pp. 1-13. [26] ______, An algorithm for coarsening unstructured meshes, Numer. Math., 73 (1996), pp. 1-36. [27] B. Bialecki and M. Dryja, Preconditioned conjugate gradi- ent multilevel methods for orthogonal spline collocation dis- cretization of the Dirichlet problem for Poisson's equation, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 1, Ni- jmegan, The Netherlands, 1996, University of Nijmegan, pp. 77-89. [28] E. F. F. Botta, A. van der Ploeg, and F. W. Wubs, A fast linear-system solver for large unstructured problems on a shared-memory parallel computer, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 1, Nijmegan, The Netherlands, 1996, University of Nijmegan, pp. 105-116. [29] V. V. Denissenko, The multilevel iteration method for 2-D problems, that simulate transfer processes with assymmetric coefficients matrix, in AMLI'96: Proceedings of the Confer- ence on Algebraic Multilevel Iteration Methods with Appli- cations, vol. 1, Nijmegan, The Netherlands, 1996, University of Nijmegan, pp. 117-125. [30] R. E. Ewing and S. Maliassov, Preconditioning techniques for mixed and nonconforming finite element methods, in AMLI'96: Proceedings of the Conference on Algebraic Mul- tilevel Iteration Methods with Applications, vol. 1, Ni- jmegan, The Netherlands, 1996, University of Nijmegan, pp. 7-22. [31] R. E. Ewing, S. Maliassov, Yu. A. Kuznetsov, and R. Lazarov, Substructure preconditioning for porous flow problems, in Finite Element Modeling of Environmental Problems, G. Garey, ed., New York, 1995, John Wiley & Sons, pp. 303-332. [32] G. Fiorentino and S. Serra, A o algebra based multiiterative solver for (block) Toeplitz systems, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 1, Nijmegan, The Netherlands, 1996, University of Nijmegan, pp. 129-140. [33] J. Fuhrman, Outlines of a modular algebraic multilevel method, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 1, Ni- jmegan, The Netherlands, 1996, University of Nijmegan, pp. 141-152. [34] K. Gustavson, Trigonometric interpretation of iterative meth- ods, in AMLI'96: Proceedings of the Conference on Alge- braic Multilevel Iteration Methods with Applications, vol. 1, Nijmegan, The Netherlands, 1996, University of Nijmegan, pp. 23-29. [35] B. Heise and M. Jung, Robust parallel Newton-multilevel methods, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 1, Nijmegan, The Netherlands, 1996, University of Ni- jmegan, pp. 153-168. [36] R. H. W. Hoppe and B. Wolmuth, Efficient numerical solu- tion of mixed finite element discretizations by adaptive mul- tilvel methods, Appl. Math., 40 (1995), pp. 227-248. [37] Yu. A. Kuznetsov, Efficient iterative solvers for elliptic finite element problems on nonmatching grids, Russ. J. Numer. Anal. Math. Modeling, 10 (1995), pp. 187-211. [38] Yu. A. Kuznetsov and S. Maliassov, Substructuring pre- conditioners for nonconforming finite element approxima- tions of second-order elliptic problems with anisotropy, Russ. J. Numer. Anal. Math. Modeling, 10 (1995), pp. 511-533. [39] Yu. A. Kuznetsov and M. H. Wheeler, Optimal order sub- structuring preconditioners for mixed finite element methods on nonmatching grids, E. W. J. Numer. Math., 3 (1995), pp. 127-143. [40] S. Maliassov, Optimal Order Preconditioners for Mixed and Nonconforming Finite Element Approximations of Elliptic Problems with Anisotropy, PhD thesis, Texas A&M, College Station, TX, 1996. [41] S. Margenov, Semi-coarsening AMLI algorithms for elastic- ity problems, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 2, Nijmegan, The Netherlands, 1996, University of Ni- jmegan, pp. 179-193. [42] G. Muratova and L. Krukier, Multigrid method for the iter- ative solution of strongly nonselfadjoint problems with dissi- pative matrix, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 2, Nijmegan, The Netherlands, 1996, University of Ni- jmegan, pp. 169-178. [43] M. Neytcheva, O. Axelsson, and K. Georgiev, An appli- cation of the AMLI method for solving convection-diffusion problems with potentialvelocity field, in AMLI'96: Proceed- ings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 2, Nijmegan, The Nether- lands, 1996, University of Nijmegan, pp. 197-210. [44] Y. Notay, An efficient algebraic multilevel preconditioner ro- bust with respect to anisotropies, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 2, Nijmegan, The Netherlands, 1996, University of Nijmegan, pp. 211-228. [45] S. Oliveira, A preconditioned multigrid subspace algorithm for computing eigenvalues and eigenvectors, in AMLI'96: Pro- ceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 2, Nijmegan, The Nether- lands, 1996, University of Nijmegan, pp. 229-232. [46] T. Rossi, Ficticious Domain Methods with Separable Precon- ditioners, PhD thesis, University of Jyv"askyla, Jyv"askyla, Finland, 1995. [47] Y. Shapira, Black box multigrid solver for definite and in- definte problems, in AMLI'96: Proceedings of the Confer- ence on Algebraic Multilevel Iteration Methods with Appli- cations, vol. 2, Nijmegan, The Netherlands, 1996, University of Nijmegan, pp. 235-250. [48] O. Shishkina, Optimality of the pseudodiagonal hierarchical preconditioner, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applica- tions, vol. 2, Nijmegan, The Netherlands, 1996, University of Nijmegan, pp. 251-258. [49] B. F. Smith, P. E. Bjorstad, and W. D. Gropp, Do- main Decomposition: Parallel Multilevel Methods for El- liptic Partial Differential Equations, Cambridge University Press, New York, 1996. [50] K. Urban, Using divergence free wavelets for the numerical solution of the Stokes problem, in AMLI'96: Proceedings of the Conference on Algebraic Multilevel Iteration Methods with Applications, vol. 2, Nijmegan, The Netherlands, 1996, University of Nijmegan, pp. 261-277. [51] P. S. Vassilevski, Multilevel preconditioning matrices and multigrid V-cycle methods, in Proceedings, 4th GAMM- Seminar Kiel, Jan. 1988, W. Hackbusch, ed., vol. 23 of Notes on Numerical Fluid Mechanics, Braunschweig, 1989, Vieweg, pp. 200-208. [52] ______, Hybrid V-cycle algebraic multilevel preconditioners, Math. Comp., 58 (1992), pp. 489-512. ------------------------------ End of MGNet Digest **************************