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

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

MathSciNet review:
930228

Full-text PDF

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]**R. E. Bank, "A comparison of two multilevel iterative methods for nonsymmetric and indefinite elliptic finite element equations,"*SIAM J. Numer. Anal.*, v. 18, 1981, pp. 724-743. MR**622706 (82f:65110)****[2]**R. E. Bank & C. C. Douglas, "Sharp estimates for multigrid rates of convergence with general smoothing and acceleration,"*SIAM J. Numer. Anal.*, v. 22, 1985, pp. 617-633. MR**795944 (86j:65037)****[3]**R. E. Bank & T. Dupont, "An optimal order process for solving elliptic finite element equations,"*Math. Comp.*, v. 36, 1981, pp. 35-51. MR**595040 (82b:65113)****[4]**D. Braess & W. Hackbusch, "A new convergence proof for the multigrid method including the*V*-cycle,"*SIAM J. Numer. Anal.*, v. 20, 1983, pp. 967-975. MR**714691 (85h:65233)****[5]**J. H. Bramble & J. E. Pasciak, "New convergence estimates for multigrid algorithms,"*Math. Comp.*, v. 49, 1987, pp. 311-329. MR**906174 (89b:65234)****[6]**A. Brandt, "Multi-level adaptive solutions to boundary-value problems,"*Math. Comp.*, v. 31, 1977, pp. 333-390. MR**0431719 (55:4714)****[7]**P. Grisvard, "Behavior of the solutions of an elliptic boundary value problem in a polygonal or polyhedral domain," in*Numerical Solution of Partial Differential Equations*, III (B. Hubbard, ed.), 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]**T. Kato,*Perturbation Theory for Linear Operators*, Springer-Verlag, New York, 1976. MR**0407617 (53:11389)****[10]**V. A. Kondrat'ev, "Boundary problems for elliptic equations with conical or angular points,"*Trans. Moscow Math. Soc.*, v. 16, 1967, pp. 227-313. MR**0226187 (37:1777)****[11]**S. G. Krein & Y. I. Petunin,*Scales of Banach spaces*, Russian Math. Surveys, vol. 21, 1966, pp. 85-160. 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 & F. Musy, "Algebraic formalization of the multigrid method in the symmetric and positive definite case--A convergence estimation for the*V*-cycle," in*Multigrid Methods for Integral and Differential Equations*(D. J. Paddon and H. Holstein, eds.), Clarendon Press, Oxford, 1985. MR**849375 (87i:65044)****[14]**J. Mandel, "Multigrid convergence for nonsymmetric, indefinite variational problems and one smoothing step," in*Proc. Copper Mtn. Conf. Multigrid Methods*, Appl. Math. Comput., 1986, pp. 201-216. MR**849837 (87i:65097)****[15]**J. Mandel,*Algebraic Study of Multigrid Methods for Symmetric, Definite Problems*. (Preprint.) MR**923402 (89d:65036)****[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.*, v. 21, 1984, pp. 255-263. MR**736329 (85h:65115)****[18]**S. F. McCormick, "Multigrid methods for variational problems: General theory for the*V*-cycle,"*SIAM J. Numer. Anal.*, v. 22, 1985, pp. 634-643. MR**795945 (86m:65030)****[19]**J. Neoas,*Les Méthodes Directes en Théorie des Équations Elliptiques*, Academia, Prague, 1967.**[20]**A. H. Schatz, "An observation concerning Ritz-Galerkin methods with indefinite bilinear forms,"*Math. Comp.*, v. 28, 1974, pp. 959-962. MR**0373326 (51:9526)****[21]**H. Yserentant, "The convergence of multi-level methods for solving finite-element equations in the presence of singularities,"*Math. Comp.*, v. 47, 1986, pp. 399-409. MR**856693 (88d:65149)**

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

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

Additional Information

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

Article copyright:
© Copyright 1988
American Mathematical Society