Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The analysis of multigrid algorithms with nonnested spaces or noninherited quadratic forms

Authors: James H. Bramble, Joseph E. Pasciak and Jinchao Xu
Journal: Math. Comp. 56 (1991), 1-34
MSC: Primary 65N22; Secondary 65N55
MathSciNet review: 1052086
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We provide a theory for the analysis of multigrid algorithms for symmetric positive definite problems with nonnested spaces and noninherited quadratic forms. By this we mean that the form on the coarser grids need not be related to that on the finest, i.e., we do not stay within the standard variational setting. In this more general setting, we give new estimates corresponding to the $ \mathcal{V}$ cycle, $ \mathcal{W}$ cycle and a $ \mathcal{V}$ cycle algorithm with a variable number of smoothings on each level. In addition, our algorithms involve the use of nonsymmetric smoothers in a novel way.

We apply this theory to various numerical approximations of second-order elliptic boundary value problems. In our first example, we consider certain finite difference multigrid algorithms. In the second example, we consider a finite element multigrid algorithm with nested spaces, which however uses a prolongation operator that does not coincide with the natural subspace imbedding. The third example gives a multigrid algorithm derived from a loosely coupled sequence of approximation grids. Such a loosely coupled grid structure results from the most natural standard finite element application on a domain with curved boundary. The fourth example develops and analyzes a multigrid algorithm for a mixed finite element method using the so-called Raviart-Thomas elements.

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

  • [1] A. K. Aziz and I. Babuška, Survey lectures on the mathematical foundations of the finite element method, Part I, The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations (A. K. Aziz, ed.), Academic Press, New York, 1972, pp. 1-362. MR 0421106 (54:9111)
  • [2] R. E. Bank and C. C. Douglas, Sharp estimates for multigrid rates of convergence with general smoothing and acceleration, SIAM J. Numer. Anal. 22 (1985), 617-633. MR 795944 (86j:65037)
  • [3] R. E. Bank and T. Dupont, An optimal order process for solving finite element equations, Math. Comp. 36 (1981), 35-51. MR 595040 (82b:65113)
  • [4] D. Braess and W. Hackbusch, A new convergence proof for the multigrid method including the V-cycle, SIAM J. Numer. Anal. 20 (1983), 967-975. MR 714691 (85h:65233)
  • [5] J. H. Bramble and J. E. Pasciak, New convergence estimates for multigrid algorithms, Math. Comp. 49 (1987), 311-329. MR 906174 (89b:65234)
  • [6] J. H. Bramble, J. E. Pasciak, and J. Xu, The analysis of multigrid algorithms for nonsymmetric and indefinite elliptic problems, Math. Comp. 51 (1988), 389-414. MR 930228 (89b:65260)
  • [7] J. H. Bramble and J. E. Pasciak, A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems, Math. Comp. 50 (1988), 1-18. MR 917816 (89m:65097a)
  • [8] A. Brandt, Multi-level adaptive solutions to boundary-value problems, Math. Comp. 31 (1977), 333-390. MR 0431719 (55:4714)
  • [9] S. C. Brenner, An optimal-order multigrid method for P1 nonconforming finite elements, Math. Comp. 52 (1989), 1-16. MR 946598 (89f:65119)
  • [10] F. Brezzi, J. Douglas, Jr., and L. D. Marini, Two families of mixed finite elements for second order elliptic problems, Numer. Math. 47 (1985), 217-235. MR 799685 (87g:65133)
  • [11] P. L. Butzer and H. Berens, Semi-groups of operators and approximation, Springer-Verlag, Berlin and New York, 1967. MR 0230022 (37:5588)
  • [12] P. G. Ciarlet, The finite element method for elliptic problems, North-Holland, New York, 1978. MR 0520174 (58:25001)
  • [13] C. C. Douglas, Multi-grid algorithms with applications to elliptic boundary-value problems, SIAM J. Numer. Anal. 21 (1984), 236-254. MR 736328 (85i:65132)
  • [14] T. Dupont and R. Scott, Polynomial approximation of functions in Sobolev spaces, Math. Comp. 34 (1980), 441-463. MR 559195 (81h:65014)
  • [15] R. Glowinski and M. F. Wheeler, Domain decomposition and mixed methods for elliptic problems, Proc. 1st Internat. Conf. on Domain Decomposition Methods, SIAM, Philadelphia, PA, 1988, pp. 144-172. MR 972516 (90a:65237)
  • [16] W. Hackbusch, Multi-grid methods and applications, Springer-Verlag, New York, 1985.
  • [17] R. B. Kellogg, Interpolation between subspaces of a Hilbert space, Technical Note BN-719, Univ. of Maryland, Inst. of Fluid Dynamics and Appl. Math., 1971.
  • [18] S. G. Kreĭn and Y. I. Petunin, Scales of Banach spaces, Russian Math. Surveys 21 (1966), 85-160. MR 0193499 (33:1719)
  • [19] J. L. Lions and E. Magenes, Problèmes aux limites non homogènes et applications, vol. 1, Dunod, Paris, 1968. MR 0247243 (40:512)
  • [20] J. Mandel, S. F. McCormick, and J. Ruge, An algebraic theory for multigrid methods for variational problems, preprint.
  • [21] J. Mandel, S. McCormick, and R. Bank, Variational multigrid theory, Multigrid Methods, (S. McCormick, ed.), SIAM, Philadelphia, PA, pp. 131-178. MR 972757
  • [22] S. F. McCormick, Multigrid methods for variational problems: Further results, SIAM J. Numer. Anal. 21 (1984), 255-263. MR 736329 (85h:65115)
  • [23] S. F. McCormick, Multigrid methods for variational problems: General theory for the V-cycle, SIAM J. Numer. Anal. 22 (1985), 634-643. MR 795945 (86m:65030)
  • [24] F. A. Milner, Mixed finite element methods for quasilinear second-order elliptic problems, Math. Comp. 44 (1985), 303-320. MR 777266 (86g:65215)
  • [25] J. Nečas, Les méthodes directes en théorie des équations elliptiques, Academia, Prague, 1967.
  • [26] P. A. Raviart and J. M. Thomas, A mixed finite element method for 2-nd order elliptic problems, Mathematical Aspects of Finite Element Methods, Lecture Notes in Math., vol. 606 (I. Galligani and E. Magenes, eds.), Springer-Verlag, New York, 1977, pp. 292-315. MR 0483555 (58:3547)
  • [27] F. Riesz and B. Sz.-Nagy, Functional analysis, Ungar, New York, 1955. MR 0071727 (17:175i)
  • [28] E. M. Stein, Singular integrals and differentiability properties of functions, Princeton Univ. Press, Princeton, NJ, 1970. MR 0290095 (44:7280)
  • [29] R. Temam, Navier-Stokes equations, North-Holland, New York, 1977. MR 769654 (86m:76003)
  • [30] R. Verfürth, A multilevel algorithm for mixed problems, SIAM J. Numer. Anal. 21 (1984), 264-271. MR 736330 (85f:65112)
  • [31] J. Xu, Theory of multilevel methods, Thesis, Cornell University, Ithaca, NY, 1989.
  • [32] S. Zhang, Multi-level iterative techniques, Thesis, Math. Res. Rep. 88020, Penn. State Univ., 1988.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65N22, 65N55

Retrieve articles in all journals with MSC: 65N22, 65N55

Additional Information

Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society