Fourier analysis of multigrid methods for general systems of PDEs

Lötstedt, Per; Gustafsson, Bertil

doi:10.1090/S0025-5718-1993-1176712-6

Fourier analysis of multigrid methods for general systems of PDEs
HTML articles powered by AMS MathViewer

by Per Lötstedt and Bertil Gustafsson PDF

Math. Comp. 60 (1993), 473-493 Request permission

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.

References

Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 431719, DOI 10.1090/S0025-5718-1977-0431719-X

Grid patching and residual smoothing for computations of steady state solutions of first order hyperbolic systems

The choice of the number of iterations in every cycle for the two-grid method

P. R. Garabedian, Estimation of the relaxation factor for small mesh size, Math. Tables Aids Comput. 10 (1956), 183–185. MR 88802, DOI 10.1090/S0025-5718-1956-0088802-7
Bertil Gustafsson and Per Lötstedt, Analysis of the multigrid method applied to first order systems, Proceedings of the Fourth Copper Mountain Conference on Multigrid Methods (Copper Mountain, CO, 1989) SIAM, Philadelphia, PA, 1989, pp. 181–233. MR 1065631
Bertil Gustafsson and Per Lötstedt, Analysis of multigrid methods for general systems of PDE, Multigrid methods, III (Bonn, 1990) Internat. Ser. Numer. Math., vol. 98, Birkhäuser, Basel, 1991, pp. 223–234. MR 1131559
Wolfgang Hackbusch, Multigrid methods and applications, Springer Series in Computational Mathematics, vol. 4, Springer-Verlag, Berlin, 1985. MR 814495, DOI 10.1007/978-3-662-02427-0
P. W. Hemker, On the order of prolongations and restrictions in multigrid procedures, J. Comput. Appl. Math. 32 (1990), no. 3, 423–429. MR 1090888, DOI 10.1016/0377-0427(90)90047-4
Antony Jameson, Solution of the Euler equations for two-dimensional transonic flow by a multigrid method, Appl. Math. Comput. 13 (1983), no. 3-4, 327–355. MR 726640, DOI 10.1016/0096-3003(83)90019-X
Antony Jameson, Computational transonics, Comm. Pure Appl. Math. 41 (1988), no. 5, 507–549. MR 948070, DOI 10.1002/cpa.3160410503

A time-accurate multiple-grid algorithm

Tosio Kato, Perturbation theory for linear operators, Die Grundlehren der mathematischen Wissenschaften, Band 132, Springer-Verlag New York, Inc., New York, 1966. MR 0203473
Peter Lancaster, Theory of matrices, Academic Press, New York-London, 1969. MR 0245579
Per Lötstedt, Grid independent convergence of the multigrid method for first-order equations, SIAM J. Numer. Anal. 29 (1992), no. 5, 1370–1394. MR 1182735, DOI 10.1137/0729079
Thomas A. Manteuffel, The Tchebychev iteration for nonsymmetric linear systems, Numer. Math. 28 (1977), no. 3, 307–327. MR 474739, DOI 10.1007/BF01389971
Wim A. Mulder, A new multigrid approach to convection problems, J. Comput. Phys. 83 (1989), no. 2, 303–323. MR 1013056, DOI 10.1016/0021-9991(89)90121-6
Youcef Saad and Martin H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986), no. 3, 856–869. MR 848568, DOI 10.1137/0907058
Klaus Stüben and Ulrich Trottenberg, Multigrid methods: fundamental algorithms, model problem analysis and applications, Multigrid methods (Cologne, 1981) Lecture Notes in Math., vol. 960, Springer, Berlin-New York, 1982, pp. 1–176. MR 685773
Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR 0158502