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) Today's editor: Craig Douglas (douglas-craig@cs.yale.edu) Volume 3, Number 7 (July 31, 1993) Today's topics: EMG93 directory/conference Book Announcement Vandewalle references Oosterlee references More References Paper on Parabolic Multigrid and Waveform Relaxation ------------------------------------------------------- Date: Fri, 30 Jul 1993 08:04:34 -0400 From: douglas-craig@cs.yale.edu (Craig Douglas) Subject: EMG93 directory/conference The 4th EMG conference was held in Amsterdam. Many people who attended went on vacation immediately afterwards so a sumary has not yet been forwarded here (hint: see you name in lights for a summary before I have to write one). Many thanks to the organizers for a very good conference. Both Piet Hemker's and Piet Wesseling's families deserve many thanks from all of us who attended. I have received a couple of papers that were submitted to Piet Hemker for inclusion in the proceedings of Fourth European Multigrid Conference. I have put them in a new directory, mgnet/EMG93. See the README.mgnet file in that directory for more information. If I do not hear of any more papers, I will print the abstracts next issue. Hopefully, Piet Hemker will look upon this as free disk space... ------------------------------------------------------- Date: Thu, 22 Jul 1993 15:31:38 +0200 (MET DST) From: Stefan.Vandewalle@cs.kuleuven.ac.be (Stefan Vandewalle) Subject: Book Announcement I would like to announce the publication of the book: "Parallel Multigrid Waveform Relaxation for Parabolic Problems" by Stefan Vandewalle, in the series Teubner-Skripten zur Numerik, B.G. Teubner Stuttgart, Germany, 1993. (16.2x23.5 cm, 247 pages, DM 39.80, ISBN 3-519-02717-8) Abstract: Waveform relaxation is a highly parallel iterative method for solving very large systems of ordinary differential equations. Over the years this method has been applied almost exclusively for the systems that model VLSI electronic circuits. In the present work the author studies waveform relaxation methods for parabolic partial differential equations of initial boundary-value and time-periodic type. It is shown both theoretically and by numerical experimentation that waveform relaxation, when accelerated by using multigrid, is a highly effective algorithm. It combines a low serial complexity with a high parallel efficiency and it is easily vectorisable. The book starts with an introductory overview of the waveform relaxation theory and practice, and provides an in-depth analysis of multigrid waveform relaxation. It discusses the parallel implementation of classical time-stepping schemes and analyses the computational complexity of waveform relaxation methods. A large number of case- studies illustrate the performance of the methods for linear and nonlinear problems. ------------------------------------------------------- Date: Thu, 22 Jul 1993 15:31:38 +0200 (MET DST) From: Stefan.Vandewalle@cs.kuleuven.ac.be (Stefan Vandewalle) Subject: Vandewalle references @article{SVandewalle_RPiessens_92, author = "Vandewalle, S. and Piessens, R.", title = "Efficient parallel algorithms for solving initial-boundary value and time-periodic parabolic partial differential equations", journal= "SIAM J. Sci. Stat. Comput.", volume = "13", year = "1992", pages = "1330--1346" } @article{SVandewalle_RPiessens_91, author = "Vandewalle, S. and Piessens, R.", title = "Numerical experiments with nonlinear multigrid waveform relaxation on a parallel processor", journal= "Applied Numerical Mathematics", volume = "8", year = "1991", pages = "149--161" } @article{SVandewalle_RPiessens_93, author = "Vandewalle, S. and Piessens, R.", title = "On dynamic iteration methods for solving time-periodic differential equations", journal= "SIAM J. Numer. Anal.", volume = "30", year = "1993", pages = "286--303" } @article{SVandewalle_RVandriessche_RPiessens_91, author = "Vandewalle, S. and Van Driessche, R. and Piessens, R.", title = "The parallel performance of standard parabolic marching schemes", journal= "Int. J. High Speed Computing", volume = "3", year = "1991", pages =""1--29" } ------------------------------------------------------- Date: Tue, 29 Jun 93 10:50:59 METDST From: Kees Oosterlee (NW)Subject: Oosterlee references C.W. Oosterlee and P. Wesseling, A multigrid method for an invariant formulation of the incompressible {N}avier-{S}tokes equations in general coordinates Comm. Appl. Num. Methods, 8 (1992), pp. 721--734 C.W. Oosterlee and P. Wesseling, A robust multigrid method for a discretization of the incompressible {N}avier-{S}tokes equations in general coordinates Impact Comp. Science and Eng., 5 (1993), pp. 128--151 C.W. Oosterlee and P. Wesseling, A multigrid method for a discretization of the incompressible {N}avier-{S}tokes equations in general coordinates In: J.B. Vos, A. Rizzi, I.L. Ryhming (Eds.), Proc. of the 9th GAMM Conf. on Num. Meth. in Fluid Mech., Ser. Notes on Num. Fluid Mech., 35 (1992), pp. 99--106, Vieweg, Braunschweig C.W. Oosterlee and P. Wesseling, A robust multigrid method for a discretization of the incompressible {N}avier-{S}tokes equations in general coordinates In: Ch. Hirsch, J. Periaux, W. Kordulla (Eds.), Proc. of the 1th Europ. Fluid Dyn. Conf., pp. 101--108, Elsevier, Amsterdam (1992). ------------------------------------------------------- Date: Wed, 28 Jul 1993 13:09:01 -0400 From: douglas-craig@cs.yale.edu (Craig Douglas) Subject: More References As noted in the last issue, I have been adding some more references to mgnet/bib/mg.bib. This is the promised second installment. As always, corrections and additions are always welcome. A. C. Irving and C. Michael Finite size effects and scaling in lattice {CP$^{N 1}$}, Phys. Lett. B, 292 (1992), pp. 392-396 Iyengar and R. K. Satteluri and A. Goyal Comparison of {S} and {V} cycles in multigrid method for linear elliptic equations with variable coefficients, Numer. Methods Partial Differential Equations, 8 (1992), pp. 113-125 Y. Jiang and C. P. Chen and P. K. Tucker Multigrid solution of unsteady {N}avier {S}tokes equations using a pressure method, Numer. Heat Transf. A, Appl., 20 (1991), pp. 81-93 T. Kalkreuter Projective block spin transformations in lattice gauge theories, Nucl. Phys. B, B376 (1992), pp. 637-660 G. King and F. C. Sze and P. Mak and T. A. Grotjohn and J. Asmussen Ion and neutral energies in a multipolar electron cyclotron resonance plasma source, J. Vac. Sci. Technol. A, Vac. Surf. Films, 10 (1992), pp. 1265-1269 M. Kocvara An algebraic study of a local multigrid method for variational problems, Appl. Math. Comput., 51 (1992), pp. 17-41 M. La~{S}cala and R. Sbrizzai and F. Torelli A pipelined-in-time parallel algorithm for transient stability analysis, IEEE Trans. Power Syst., 6 (1991), pp. 715-722 A. Lanza Self gravitating thin disks around rapidly rotating black holes, Astrophys. J., 389 (1992), pp. 141-156 M. L. Laursen and J. Smit and J. C. Vink Multigrid updating of {U}(1) gauge fields, Phys. Lett. B, 262 (1991), pp. 467-471 C. Liu and Z. Liu and S. F. McCormick Multilevel adaptive methods for incompressible flow in grooved channels, J. Comput. Appl. Math., 38 (1991), pp. 283-295 J. C. Luo Formulation of the finite element method by domain decomposition, Comput. Struct., 43 (1992), pp. 751-760 R. Mattis and A. Haghighat Domain decomposition of a two-dimensional {S$^n$} method, Nucl. Sci. Eng., 111 (1992), pp. 180-196 D. J. Mavriplis Three-dimensional unstructured multigrid for the {E}uler equations, AIAA J., 30 (1992), pp. 1753-1761 D. J. Mavriplis Turbulent flow calculations using unstructured and adaptive meshes, Int. J. Numer. Methods Fluids, 13 (1991), pp. 1131-1152 R. McLachlan A steady separated viscous corner flow, J. Fluid Mech., 231 (1991), pp. 1-34 R. Meyer Spasche and B. Fornberg Discretization errors at free boundaries of the {G}rad {S}chluter {S}hafranov equation, Numer. Math., 59 (1991), pp. 683-710 V. Mikulinsky Multigrid treatment of thin domains, SIAM J. Sci. Stat. Comput., 12 (1991), pp. 940-949 M. Napolitano Efficient solution of two-dimensional steady separated flows, Computers & Fluids, 20 (1991), pp. 213-222 C. W. Oehlrich and A. Quick Performance evaluation of a communication system for transputer networks based on monitored event traces, Comput. Archit. News, 19 (1991), pp. 202-211 G. Palma Renormalized loop expansion to compute finite size effects of the constraint effective potential, Z. Phys. C, Part. Fields, 54 (1992), pp. 679-682 G. W. Parker What is the capacitance of parallel plates?, Comput. Phys., 5 (1991), pp. 534-540 J. Peraire and J. Peiro and K. Morgan and O. Hassan and O. C. Zienkiewicz Applications of supercomputers in aerodynamics, Rev. Int. Metodos Numer. para Calc. Diseno Ing., 8 (1992), pp. 215-233 C. Y. Perng and R. L. Street Coupled multigrid-domain-splitting technique for simulating incompressible flows in geometrically complex domains, Int. J. Numer. Methods Fluids, 13 (1991), pp. 269-286 A. L. Perkins Tailored domain decomposition, Adv. Eng. Softw., 14 (1992), pp. 145-149 T. von Petersdorff and E. P. Stephan Multigrid solvers and preconditioners for first kind integral equations, Numer. Methods Partial Differential Equations, 8 (1992), pp. 443-450 G. Pini Domain decomposition and nested grids in a parallel environment, Supercomputer, 9 (1992), pp. 22-28 A. Plaza and L. Ferragut and R. Montenegro Derefinement algorithms of nested meshes, IFIP Trans. A, Comput. Sci. Technol., A12 (1992), pp. 409-415 W. H. Press and S. A. Teukolsky Multigrid methods for boundary value problems {I}, Comput. Phys., 5 (1991), pp. 514-519 P. A. Rubini and H. A. Becker and E. W. Grandmaison and A. Pollard and A. Sobiesiak and C. Thurgood Multigrid acceleration of three dimensional, turbulent, variable density flows, Numer. Heat Transf. B, Fundam., 22 (1992), pp. 163-177 S. Sauter and G. Wittum A multigrid method for the computation of eigenmodes of closed water basins, Impact Comput. Sci. Eng., 4 (1992), pp. 124-152 M. Schafer Numerical solution of the time dependent axisymmetric {B}oussinesq equations on processor arrays, SIAM J. Sci. Stat. Comput., 13 (1992), pp. 1377-1393 J. N. Shadid and R. S. Tuminaro Sparse iterative algorithm software for largescale {MIMD} machines: an initial discussion and implementation, Concurrency, Pract. Exp., 4 (1992), pp. 481-497 W. Shyy and M. E. Braaten and D. L. Burrus Study of three-dimensional gas-turbine combustor flows, Int. J. Heat Mass Transfer, 32 (1989), pp. 1155-1164 R. A. Smith and A. Weiser Semicoarsening multigrid on a hypercube, SIAM J. Sci. Stat. Comput., 13 (1992), pp. 1314-1329 G. Stoyan and R. Stoyan Colouring the discretization graphs arising in the multigrid method, Comput. Math. Appl., 22 (1991), pp. 55-62 R. C. Swanson and R. Radespiel Cell centered and cell vertex multigrid schemes for the {N}avier-{S}tokes equations, AIAA J., 29 (1991), pp. 697-703 Editor's Note: mgnet/bib/mg.bib has the BibTeX entries. You, too, can ------------- have your published papers in there by just sending me e-mail with the citations in any reasonable format. ------------------------------------------------------- Date: Fri, 30 Jul 93 13:04:44 EDT From: worley@haven.EPM.ORNL.GOV (Pat Worley) Subject: Paper on Parabolic Multigrid and Waveform Relaxation An Algorithm with Polylog Parallel Complexity for Solving Parabolic Partial Differential Equations Graham Horton (1) Stefan Vandewalle (2) Patrick Worley (3) Abstract: The standard numerical algorithms for solving parabolic partial differential equations are inherently sequential in the time direction. This paper describes an algorithm for the time-accurate solution of certain classes of parabolic partial differential equations that can be parallelized in both time and space. It has a serial complexity that is proportional to the serial complexities of the best known algorithms. The algorithm is a variant of the multigrid waveform relaxation method where the scalar ordinary differential equations that make up the kernel of computation are solved using a cyclic reduction type algorithm. Experimental results obtained on a massively parallel multiprocessor are presented. (1) Lehrstuhl f\"ur Rechnerstrukturen (IMMD 3), Universit\"at Erlangen-N\"urnberg, Martensstrasse 3, D-8520 Erlangen, Federal Republic of Germany. E-mail: graham@immd3.informatik.uni-erlangen.de (2) Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, B-3001 Leuven (Heverlee), Belgium. E-mail: stefan@cs.kuleuven.ac.be (3) Mathematical Sciences Section, Oak Ridge National Laboratory, P.O. Box 2008, Oak Ridge, Tennessee 37831-6367, USA. E-mail: worley@msr.epm.ornl.gov Editor's Note: mgnet/papers/Horton_Vandewalle_Worley/mgwrcr.{dvi,ps} ------------- mgnet/papers/Horton_Vandewalle_Worley/mgwrcr.abstract ------------------------------ End of MGNet Digest **************************