Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

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.

References [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

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

Additional Information

Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society