Fourier analysis of multigrid methods for general systems of PDEs

Authors:
Per Lötstedt and Bertil Gustafsson

Journal:
Math. Comp. **60** (1993), 473-493, S3

MSC:
Primary 65N55; Secondary 65F10, 65N12

DOI:
https://doi.org/10.1090/S0025-5718-1993-1176712-6

MathSciNet review:
1176712

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Most iteration methods for solving boundary value problems can be viewed as approximations of a time-dependent differential equation. In this paper we show that the multigrid method has the effect of increasing the time-step for the smooth part of the solution leading back to an increase of the convergence rate. For the nonsmooth part the convergence is an effect of damping. Fourier analysis is used to find the relation between the convergence rate for multigrid methods and singlegrid methods. The analysis is performed for general partial differential equations and an arbitrary number of grids. The difference in the behavior of the iterations between first- and second-order equations is discussed. The theoretical results are confirmed in simple numerical experiments.

**[1]**A. Brandt,*Multi-level adaptive solutions to boundary-value problems*, Math. Comp.**31**(1977), 333-390. MR**0431719 (55:4714)****[2]**R. Enander,*Grid patching and residual smoothing for computations of steady state solutions of first order hyperbolic systems*, Ph.D. thesis, Dept. of Scientific Computing, Uppsala Univeristy, Uppsala, 1991.**[3]**L. Ferm,*The choice of the number of iterations in every cycle for the two-grid method*, Report 139, Dept. of Scientific Computing, Uppsala University, Uppsala, 1991.**[4]**P. R. Garabedian,*Estimation of the relaxation factor for small mesh size*, MTAC**10**(1956), 183-185. MR**0088802 (19:583a)****[5]**B. Gustafsson and P. Lötstedt,*Analysis of the multigrid method applied to first order systems*, Proc. Fourth Copper Mountain Conf. on Multigrid Methods (J. Mandel et al., eds.), SIAM, Philadelphia, PA, 1989, pp. 181-233. MR**1065631 (91g:65278)****[6]**-,*Analysis of multigrid methods for general systems of PDE*, Multigrid Methods III (W. Hackbusch and U. Trottenberg, eds.), Birkhäuser Verlag, Basel, 1991, pp. 223-234. MR**1131559 (92f:65111)****[7]**W. Hackbusch,*Multigrid methods and applications*, Springer-Verlag, Berlin, Heidelberg, 1985. MR**814495 (87e:65082)****[8]**P. W. Hemker,*On the order of prolongations and restrictions in multigrid procedures*, J. Comput. Appl. Math.**32**(1990), 423-429. MR**1090888 (91m:65295)****[9]**A. Jameson,*Solution of the Euler equations for two-dimensional transonic flow by a multigrid method*, Appl. Math. Comput.**13**(1983), 327-355. MR**726640 (85f:76011)****[10]**-,*Computational transonics*, Comm. Pure Appl. Math.**41**(1988), 507-549. MR**948070 (89k:76068)****[11]**D. C. Jespersen,*A time-accurate multiple-grid algorithm*, AIAA paper 85-1493-CP, (1985).**[12]**T. Kato,*Perturbation theory for linear operators*, Springer-Verlag, New York, 1966. MR**0203473 (34:3324)****[13]**P. Lancaster,*Theory of matrices*, Academic Press, New York, 1969. MR**0245579 (39:6885)****[14]**P. Lötstedt,*Grid independent convergence of the multigrid method for first-order equations*, SIAM J. Numer. Anal.**29**(1992), 1370-1394. MR**1182735 (93g:65076)****[15]**T. A. Manteuffel,*The Tchebychev iteration for nonsymmetric linear systems*, Numer. Math.**28**(1977), 307-327. MR**0474739 (57:14373)****[16]**W. A. Mulder,*A new multigrid approach to convection problems*, J. Comput. Phys.**83**(1989), 303-323. MR**1013056 (90f:76013)****[17]**Y. Saad and M. H. Schultz,*GMRES*:*A generalized minimal residual algorithm for solving nonsymmetric linear systems*, SIAM J. Sci. Statist. Comput.**7**(1986), 856-869. MR**848568 (87g:65064)****[18]**K. Stüben and U. Trottenberg,*Multigrid methods*:*Fundamental algorithms, model problem analysis and applications*, Multigrid Methods (Proc., Köln-Porz, 1981), (W. Hackbusch and U. Trottenberg, eds.), Lecture Notes in Math., vol. 960, Springer-Verlag, Berlin, pp. 1-176. MR**685773 (84m:65129)****[19]**R. S. Varga,*Matrix iterative analysis*, Prentice-Hall, Englewood Cliffs, NJ, 1962. MR**0158502 (28:1725)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65N55,
65F10,
65N12

Retrieve articles in all journals with MSC: 65N55, 65F10, 65N12

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1993-1176712-6

Article copyright:
© Copyright 1993
American Mathematical Society