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 -cycle and the -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 -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 -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**, 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**, 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**, 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**, 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**, 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**, 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*, Numerical solution of partial differential equations, III (Proc. Third Sympos. (SYNSPADE), Univ. Maryland, College Park, Md., 1975) Academic Press, New York, 1976, pp. 207–274. MR**0466912****[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-New York, 1976. Grundlehren der Mathematischen Wissenschaften, Band 132. MR**0407617****[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****[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****[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****[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**, 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**, 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**, 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**, 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**, 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**, 10.1090/S0025-5718-1986-0856693-9

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

Retrieve articles in all journals with MSC: 65N30, 65F10

Additional Information

DOI:
http://dx.doi.org/10.1090/S0025-5718-1988-0930228-6

Article copyright:
© Copyright 1988
American Mathematical Society