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 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. 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.
- 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 D. C. Jespersen, A time-accurate multiple-grid algorithm, AIAA paper 85-1493-CP, (1985).
- 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
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 60 (1993), 473-493
- MSC: Primary 65N55; Secondary 65F10, 65N12
- DOI: https://doi.org/10.1090/S0025-5718-1993-1176712-6
- MathSciNet review: 1176712