Abstract
The advent of parallel computers has led to the development of new solution algorithms for time-dependent partial differential equations. Two recently developed methods, multigrid waveform relaxation and time-parallel multigrid, have been designed to solve parabolic partial differential equations on many time-levels simultaneously. This paper compares the convergence properties of these methods, based on the results of an exponential Fourier mode analysis for a model problem.
Zusammenfassung
Die Erscheinung von Parallelrechnern hat zur Entwicklung neuer Lösungsverfahren for zeitabhängige partielle Differentialgleichungen geführt. Zwei der in letzter Zeit entwickelten Verfahren — die Mehrgitter-Wellenformrelaxations-Methode und die zeitparallele Mehrgittermethode —haben zum Ziel, die Lösung zu vielen verschiedenen diskreten Zeitpunkten simultan zu berechnen. In dieser Arbeit wird anhand der Ergebnisse einer Fourier-Analyse für ein Modell-problem das Konvergenzverhalten beider Methoden verglichen.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bastian, P., Burmeister, J., Horton, G.: Implementation of a parallel multigrid method for parabolic partial differential equations. In: Parallel algorithms for PDEs (Proceedings of the 6th GAMM Seminar Kiel, January 19–21, 1990) (Hackbusch, W., ed.), pp. 18–27. Wiesbaden: Vieweg 1990.
Brandt, A.: Multi-level adaptive solutions to boundary-value problems. Math. Comp.31, 333–390 (1977).
Burmeister, J.: Paralleles Lösen diskreter parabolischer Probleme mit Mehrgittertechniken. Diplomarbeit, Universität Kiel, 1985.
Burmeister, J., Horton, G.: Time-parallel multigrid solution of the Navier-Stokes equations. In: Multigrid methods III (Proceedings of the third European Multigrid Conference, Bonn, 1990) (Hackbusch, W., Trottenberg, U. eds.) number 98 in ISNM, pp. 155–166. Basel: Birkhaüser 1991.
Hackbusch, W.: Parabolic multi-grid methods. In: Computing methods in applied sciences and engineering VI (Glowinski, R., Lions, J.-L., eds.) pp. 189–197. Amsterdam: North-Holland 1984.
Horton, G.: Time-parallel multigrid solution of the Navier-Stokes equations. In: Applications of supercomputers in engineering (Brebbia, C., ed.). Amsterdam: Elsevier 1991.
Horton, G.: The time-parallel multigrid method. Comm. Appl. Numer. Meth.8, 585–595 (1992).
Horton, G., Knirsch, R.: A time-parallel multigrid-extrapolation method for parabolic partial differential equations. Parallel Comput.18, 21–29 (1992).
Horton, G., Vandewalle, S.: A space-time multigrid method for parabolic P.D.E.s. Technical Report IMMD 3, 6/93, Universität Erlangen-Nürnberg, Martensstrasse 3, D-91058 Erlangen, Germany, July 1993. (to appear in SIAM J. Sci. Comput.).
Horton, G., Vandewalle, S., Worley, P.: An algorithm with polylog parallel complexity for solving parabolic partial differential equations. Technical Report IMMD 3, 8/93, Universität Erlangen-Nürnberg, Martensstrasse 3, D-91058 Erlangen Germany, July 1993 (to appear in SIAM J. Sci. Comput.).
Janssen, J., Vandewalle, S.: Multigrid waveform relaxation on spatial finite element meshes: the continuous-time case. Technical Report TW 201, Katholieke Universiteit Leuven, Department of Computer Science, Celestijnenlaan 200A, B-3001 Leuven, Belgium, November 1993 (to appear in SIAM J. Num. Anal.).
Janssen, J., Vandewalle, S.: Multigrid waveform relaxation on spatial finite element meshes: the discrete-time case. Technical Report CRPC-94-8, California Institute of Technology, Pasadena, CA 91125, May 1994 (submitted to SIAM J. Sci. Comput.).
Lubich, C., Ostermann, A.: Multigrid dynamic iteration for parabolic equations. BIT27, 216–234 (1987).
Oosterlee, C., Wesseling, P.: Multigrid schemes for time-dependent incompressible Navier-Stokes equations. Impact Comput Sci. Eng.5, 153–175 (1993).
Stüben, K., Trottenberg, U.: Multigrid methods fundamental algorithms, model problem analysis and applications. In: Multigrid methods (Hackbusch, W., Trottenberg, U., eds.), pp. 1–176. Berlin, Heidelberg, New York: Springer 1982 (Lecture Notes in Mathematics vol. 960).
Vandewalle, S., Piessens, R.: Numerical experiments with nonlinear multigrid waveform relaxation on a parallel processor. Appl. Numer. Math.8, 149–161 (1991).
Vandewalle, S., Piessens, R.: Efficient parallel algorithms for solving initial-boundary value and time-periodic parabolic partial differential equations. SIAM J. Sci. Stat. Comput.13, 1330–1346 (1992).
Vandewalle, S., Piessens, R.: On dynamic iteration methods for solving time-periodic differential equations. SIAM J. Numer. Anal.30, 286–303 (1993).
Vandewalle, S., Van de Velde, E.: Space-time concurrent multigrid waveform relaxation. Ann. Numer. Math.1, 347–363 (1994).
Wesseling, P.: A survey of Fourier smoothing analysis results. In: Parallel algorithms for PDEs (Proceedings of the 6th GAMM Seminar Kiel, January 19–21, 1990), (Hackbusch, W., ed.), pp. 105–127. Wiesbaden: Vieweg 1990.
Wesseling, P.: An introduction to multigrid methods. Chichester: J. Wiley, 1992.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Vandewalle, S., Horton, G. Fourier mode analysis of the multigrid waveform relaxation and time-parallel multigrid methods. Computing 54, 317–330 (1995). https://doi.org/10.1007/BF02238230
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02238230