The analysis of multigrid algorithms for nonsymmetric and indefinite elliptic problems

Bramble, James H.; Pasciak, Joseph E.; Xu, Jinchao

doi:10.1090/S0025-5718-1988-0930228-6

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-6842(online) ISSN 0025-5718(print)

The analysis of multigrid algorithms for nonsymmetric and indefinite elliptic problems

Authors: James H. Bramble, Joseph E. Pasciak and Jinchao Xu
Journal: Math. Comp. 51 (1988), 389-414
MSC: Primary 65N30; Secondary 65F10
MathSciNet review: 930228
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove some new estimates for the convergence of multigrid algorithms applied to nonsymmetric and indefinite elliptic boundary value problems. We provide results for the so-called 'symmetric' multigrid schemes. We show that for the variable $\mathcal{V}$ -cycle and the $\mathcal{W}$ -cycle schemes, multigrid algorithms with any amount of smoothing on the finest grid converge at a rate that is independent of the number of levels or unknowns, provided that the initial grid is sufficiently fine. We show that the $\mathcal{V}$ -cycle algorithm also converges (under appropriate assumptions on the coarsest grid) but at a rate which may deteriorate as the number of levels increases. This deterioration for the $\mathcal{V}$ -cycle may occur even in the case of full elliptic regularity. Finally, the results of numerical experiments are given which illustrate the convergence behavior suggested by the theory.

[1] Randolph E. Bank, A comparison of two multilevel iterative methods for nonsymmetric and indefinite elliptic finite element equations, SIAM J. Numer. Anal. 18 (1981), no. 4, 724–743. MR 622706 (82f:65110), http://dx.doi.org/10.1137/0718048
[2] Randolph E. Bank and Craig C. Douglas, Sharp estimates for multigrid rates of convergence with general smoothing and acceleration, SIAM J. Numer. Anal. 22 (1985), no. 4, 617–633. MR 795944 (86j:65037), http://dx.doi.org/10.1137/0722038
[3] Randolph E. Bank and Todd Dupont, An optimal order process for solving finite element equations, Math. Comp. 36 (1981), no. 153, 35–51. MR 595040 (82b:65113), http://dx.doi.org/10.1090/S0025-5718-1981-0595040-2
[4] D. Braess and W. Hackbusch, A new convergence proof for the multigrid method including the 𝑉-cycle, SIAM J. Numer. Anal. 20 (1983), no. 5, 967–975. MR 714691 (85h:65233), http://dx.doi.org/10.1137/0720066
[5] James H. Bramble and Joseph E. Pasciak, New convergence estimates for multigrid algorithms, Math. Comp. 49 (1987), no. 180, 311–329. MR 906174 (89b:65234), http://dx.doi.org/10.1090/S0025-5718-1987-0906174-X
[6] Achi Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), no. 138, 333–390. MR 0431719 (55 #4714), http://dx.doi.org/10.1090/S0025-5718-1977-0431719-X
[7] Pierre Grisvard, Behavior of the solutions of an elliptic boundary value problem in a polygonal or polyhedral domain, Sympos. (SYNSPADE), Univ. Maryland, College Park, Md., 1975) Academic Press, New York, 1976, pp. 207–274. MR 0466912 (57 #6786)
[8] W. Hackbusch, Multi-Grid Methods and Applications, Springer-Verlag, New York, 1985.
[9] Tosio Kato, Perturbation theory for linear operators, 2nd ed., Springer-Verlag, Berlin, 1976. Grundlehren der Mathematischen Wissenschaften, Band 132. MR 0407617 (53 #11389)
[10] V. A. Kondrat′ev, Boundary value problems for elliptic equations in domains with conical or angular points, Trudy Moskov. Mat. Obšč. 16 (1967), 209–292 (Russian). MR 0226187 (37 #1777)
[11] S. G. Kreĭn and Ju. I. Petunin, Scales of Banach spaces, Uspehi Mat. Nauk 21 (1966), no. 2 (128), 89–168 (Russian). MR 0193499 (33 #1719)
[12] J. L. Lions & E. Magenes, Problèmes aux Limites non Homogènes et Applications, Dunod, Paris, 1968.
[13] J.-F. Maitre and F. Musy, Algebraic formalisation of the multigrid method in the symmetric and positive definite case—a convergence estimation for the 𝑉-cycle, Multigrid methods for integral and differential equations (Bristol, 1983), Inst. Math. Appl. Conf. Ser. New Ser., vol. 3, Oxford Univ. Press, New York, 1985, pp. 213–223. MR 849375 (87i:65044)
[14] Jan Mandel, Multigrid convergence for nonsymmetric, indefinite variational problems and one smoothing step, Appl. Math. Comput. 19 (1986), no. 1-4, 201–216. Second Copper Mountain conference on multigrid methods (Copper Mountain, Colo., 1985). MR 849837 (87i:65097), http://dx.doi.org/10.1016/0096-3003(86)90104-9
[15] Jan Mandel, Algebraic study of multigrid methods for symmetric, definite problems, Appl. Math. Comput. 25 (1988), no. 1, 39–56. MR 923402 (89d:65036), http://dx.doi.org/10.1016/0096-3003(88)90063-X
[16] J. Mandel, S. F. McCormick & J. Ruge, An Algebraic Theory for Multigrid Methods for Variational Problems. (Preprint.)
[17] S. F. McCormick, Multigrid methods for variational problems: further results, SIAM J. Numer. Anal. 21 (1984), no. 2, 255–263. MR 736329 (85h:65115), http://dx.doi.org/10.1137/0721018
[18] S. F. McCormick, Multigrid methods for variational problems: general theory for the 𝑉-cycle, SIAM J. Numer. Anal. 22 (1985), no. 4, 634–643. MR 795945 (86m:65030), http://dx.doi.org/10.1137/0722039
[19] J. Neoas, Les Méthodes Directes en Théorie des Équations Elliptiques, Academia, Prague, 1967.
[20] Alfred H. Schatz, An observation concerning Ritz-Galerkin methods with indefinite bilinear forms, Math. Comp. 28 (1974), 959–962. MR 0373326 (51 #9526), http://dx.doi.org/10.1090/S0025-5718-1974-0373326-0
[21] Harry Yserentant, The convergence of multilevel methods for solving finite-element equations in the presence of singularities, Math. Comp. 47 (1986), no. 176, 399–409. MR 856693 (88d:65149), http://dx.doi.org/10.1090/S0025-5718-1986-0856693-9

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|