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) Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) Volume 2, Number 8 (August 29, 1992) Today's topics: Unstructured grids replies (3) Paper related to multigrid for unstructured grids Cyclic reduction and multigrid Paper on the robustness and efficiency of the fully adaptive multigrid method ------------------------------------------------------- Date: Wed, 29 Jul 92 19:25:34 MET DST From: Johan.DeKeyser@cs.kuleuven.ac.be (Johan De Keyser) Subject: Multigrid for unstructured meshes (in reply to your mgnet message) Hi, In reply to your question about multigrid for unstructured meshes, I dug up the following references : - Unstructured Multigridding by Volume Agglomeration, Lallemand, M.-H. and Steve, H. and Dervieux A., INRIA, Rapports de Recherche 1224, Sophia Antipolis, 1990 - The design and implementation of a parallel unstructured Euler solver using software primitives, Das, R. and Mavriplis, D. and Saltz, J. and Gupta, S. and Ponnusamy, R., Proceedings of the 30th Aerospace Sciences Meeting and Exhibit, Paper AIAA-92-0562, 1992 - Accurate multigrid solution of the Euler equations on unstructured and adaptive meshes, Mavriplis D., ICASE report 88-40, 1988 and some of my own work - Incremental Mapping for Solution-Adaptive Multigrid Hierarchies, De Keyser, J. and Roose, D., Proceedings of the Scalable High Performance Computing Conference 92, IEEE Computer Society Press, pp. 401-408, 1992 Personally, I am interested in the numerical aspects of such multigrid techniques, and in their implementation on distributed memory parallel computers (a.o. the load balancing problem). I have some tech reports regarding this work; I can send them to you if you're interested. ------------------------------------------------------- Date: Wed, 29 Jul 92 23:17:34 CDT From: groucho!scott@math.UH.EDU ("L. Ridgway Scott") Subject: unstructured grids One paper that may be of interest to you is by me and Shangyou Zhang, Higher Dimensional Non-nested Multigrid Methods, Math. Comp. 58 (1992), 457--466. Grids in different levels are allowed to be only weakly related, yet convergence still holds. Shangyou has written a code implementing non-nested multigrid in 3-D; the key point is to be able to construct inter-grid transfers efficiently, so only a limited class of non-nested refinements have been implemented so far. For more information: Ridgway Scott - scott@uh.edu Shangyou Zhang - szhang@math.udel.edu ------------------------------------------------------- Date: Fri, 21 Aug 1992 18:10:31 +0200 From: Ulrich Ruede Subject: Re: unstructured multigrid In the mgnet Digest of July 29, 1992 (V2N7) Horst Simon (simon@nas.nasa.gov) has asked about ideas and references for multigrid methods on unstructured grids. Most multigrid methods for unstructured grids at least assume a nested (or almost nested) hierarchy of meshes. The only fully unstructured mesh approach I can remember goes back to Loehner and Morgan: @inproceedings{Loehner86a, author = {R. L\"{o}hner and K. Morgan}, title = "Unstructured Multigrid Methods", booktitle = {Multigrid Methods: Special Topics and Applications, Papers presented at the 2nd European Conference on Multigrid Methods, Cologne, October 1-4, 1985}, year = "1986", note = "GMD Studien Vol. 110", } For nested, unstructured meshes there is the work by Randy Bank (the PLTMG package), Rivara, Mitchell, and myself (papers are available by ftp from mgnet). The work done for hierarchical basis and BPX preconditioners is closely related, though multigrid purists may not accept it as *real* multigrid. There are many theoretical papers, but working codes are less plentiful. Besides PLTMG, I know about the program by Peter Leinen (peter@tue-num2.mathematik.uni-tuebingen.de) and the program by the group at the Konrad Zuse Zentrum in Berlin (deuflhard@sc.zib-berlin.dbp.de). My own code exists as a prototype and is currently being redesigned. In this field there is much work in progress, and I hope that the other people working in unstructured multigrid methods will respond directly. If unstructured grids must be coarsened, algebraic multigrid may be a good alternative. Ulrich Ruede ------------------------------------------------------- Date: Wed, 29 Jul 92 19:58:56 MET DST From: Johan.DeKeyser@cs.kuleuven.ac.be (Johan De Keyser) Subject: Paper related to multigrid for unstructured grids Hi, I am putting a report "imap.ps" on the mgnet/incoming directory. Sorry it is in postscript (quite large) because I included some ps pictures. This report discusses parallelization of an unstructured multigrid solver (for a simple linear hyperbolic equation), especially the load balancing issues involved in this particular case. The load balancing problem is solved by applying suitable partitioning and mapping techniques. I am currently experimenting with a parallel unstructured grid FAS-cycle for the Euler equations, but I have not yet found the time to write things down ... As soon as I do, I'll let you know. Editor's Note: This paper can be found in mgnet/papers/DeKeyser/imaps.ps ------------- Partitioning and Mapping Adaptive Multigrid Hierarchies on Distributed Memory Computers Johan De Keyser and Dirk Roose johandk@cs.kuleuven.ac.be Feb 1992 Report TW166 Department of Computer Science Katholieke Universiteit Leuven Celestijnenlaan 200A 3001 Heverlee Belgium Keywords : multigrid, finite volumes, data parallelism, load balancing, distributed memory computers Abstract : The full multigrid method uses a hierarchy of successively finer grids. In a solution-adaptive grid hierarchy each grid is obtained by adaptive refinement of the grid on the previous level. On a distributed memory multiprocessor, each grid level must be partitioned and mapped so as to minimize the multigrid cycle execution time. In this report several grid partitioning and load (re)mapping strategies that deal with this problem are compared. The performance of such parallel adaptive multigrid algorithms has been evaluated on an iPSC hypercube for an irregular finite volume discretization of a linear first-order hyperbolic partial differential equation on a two-dimensional domain. ------------------------------------------------------- Date: Wed, 12 Aug 92 09:01:45 PDT From: holst@mercury.llnl.gov (Michael Holst) Subject: Cyclic reduction and multigrid Cc: holst@cs.uiuc.edu Do you know if anyone has worked out the connection between cyclic reduction and multigrid (in dimensions > 1) ?? Thanks for any help you can provide, -mike Editor's Note: I think many readers would like to know this, too. ------------- Please cc this list. ------------------------------------------------------- Date: Fri, 21 Aug 1992 17:19:12 +0200 From: Ulrich Ruede Subject: new paper downloaded to mgnet I've downloaded a short paper "On the robustness and efficiency of the fully adaptive multigrid method" to the mgnet ftp repository. The paper has been submitted for the Proceedings of the Sixth International Conference on Domain Decomposition in Science and Engineering On the mgnet the submission consists of a file robust.abstract containing the abstract as a plain ascii file, and the file robust.dvi.Z that contains the full paper as a compressed dvi-file. On the Robustness and Efficiency of the Fully Adaptive Multigrid Method Ulrich Ruede Institut fuer Informatik Technische Universitaet Muenchen Arcisstr. 21, D-8000 Muenchen 2, Germany ruede@informatik.tu-muenchen.de AMS Classifications: 65N55, 65N15, 65N50} Keywords: fully adaptive multigrid, mesh refinement, virtual global grids, error estimates, multilevel additive Schwarz method ABSTRACT The fully adaptive multigrid method (FAMe) is a finite element based elliptic solver integrating self-adaptivity, error estimation and efficient iterative solution. Refined elements are not restricted to predetermined regions and need not be grouped in patches. Instead, whether an element is refined, is decided individually for each element using an integrated error indicator. The refinement process induces a multilevel structure and therefore a natural decomposition of the solution space into a nested sequence. This can be exploited to define an efficient solver and error estimator. Editor's Note: This paper can be found in mgnet/papers/Ruede/robust.dvi.Z ------------- ------------------------------ End of MGNet Digest **************************