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

HTML articles powered by AMS MathViewer

- by James H. Bramble, Joseph E. Pasciak and Jinchao Xu PDF
- Math. Comp.
**56**(1991), 1-34 Request permission

## 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

- Ivo Babuška and A. K. Aziz,
*Survey lectures on the mathematical foundations of the finite element method*, The mathematical foundations of the finite element method with applications to partial differential equations (Proc. Sympos., Univ. Maryland, Baltimore, Md., 1972) Academic Press, New York, 1972, pp. 1–359. With the collaboration of G. Fix and R. B. Kellogg. MR**0421106** - 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**, DOI 10.1137/0722038 - 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**, DOI 10.1090/S0025-5718-1981-0595040-2 - D. Braess and W. Hackbusch,
*A new convergence proof for the multigrid method including the $V$-cycle*, SIAM J. Numer. Anal.**20**(1983), no. 5, 967–975. MR**714691**, DOI 10.1137/0720066 - James H. Bramble and Joseph E. Pasciak,
*New convergence estimates for multigrid algorithms*, Math. Comp.**49**(1987), no. 180, 311–329. MR**906174**, DOI 10.1090/S0025-5718-1987-0906174-X - James H. Bramble, Joseph E. Pasciak, and Jinchao Xu,
*The analysis of multigrid algorithms for nonsymmetric and indefinite elliptic problems*, Math. Comp.**51**(1988), no. 184, 389–414. MR**930228**, DOI 10.1090/S0025-5718-1988-0930228-6 - James H. Bramble and Joseph E. Pasciak,
*A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems*, Math. Comp.**50**(1988), no. 181, 1–17. MR**917816**, DOI 10.1090/S0025-5718-1988-0917816-8 - Achi Brandt,
*Multi-level adaptive solutions to boundary-value problems*, Math. Comp.**31**(1977), no. 138, 333–390. MR**431719**, DOI 10.1090/S0025-5718-1977-0431719-X - Susanne C. Brenner,
*An optimal-order multigrid method for $\textrm {P}1$ nonconforming finite elements*, Math. Comp.**52**(1989), no. 185, 1–15. MR**946598**, DOI 10.1090/S0025-5718-1989-0946598-X - Franco Brezzi, Jim Douglas Jr., and L. D. Marini,
*Two families of mixed finite elements for second order elliptic problems*, Numer. Math.**47**(1985), no. 2, 217–235. MR**799685**, DOI 10.1007/BF01389710 - Paul L. Butzer and Hubert Berens,
*Semi-groups of operators and approximation*, Die Grundlehren der mathematischen Wissenschaften, Band 145, Springer-Verlag New York, Inc., New York, 1967. MR**0230022** - Philippe G. Ciarlet,
*The finite element method for elliptic problems*, Studies in Mathematics and its Applications, Vol. 4, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. MR**0520174** - Craig C. Douglas,
*Multigrid algorithms with applications to elliptic boundary value problems*, SIAM J. Numer. Anal.**21**(1984), no. 2, 236–254. MR**736328**, DOI 10.1137/0721017 - Todd Dupont and Ridgway Scott,
*Polynomial approximation of functions in Sobolev spaces*, Math. Comp.**34**(1980), no. 150, 441–463. MR**559195**, DOI 10.1090/S0025-5718-1980-0559195-7 - Roland Glowinski and Mary Fanett Wheeler,
*Domain decomposition and mixed finite element methods for elliptic problems*, First International Symposium on Domain Decomposition Methods for Partial Differential Equations (Paris, 1987) SIAM, Philadelphia, PA, 1988, pp. 144–172. MR**972516**
W. Hackbusch, - 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** - J.-L. Lions and E. Magenes,
*Problèmes aux limites non homogènes et applications. Vol. 1*, Travaux et Recherches Mathématiques, No. 17, Dunod, Paris, 1968 (French). MR**0247243**
J. Mandel, S. F. McCormick, and J. Ruge, - J. Mandel, S. McCormick, and R. Bank,
*Variational multigrid theory*, Multigrid methods, Frontiers Appl. Math., vol. 3, SIAM, Philadelphia, PA, 1987, pp. 131–177. MR**972757** - S. F. McCormick,
*Multigrid methods for variational problems: further results*, SIAM J. Numer. Anal.**21**(1984), no. 2, 255–263. MR**736329**, DOI 10.1137/0721018 - S. F. McCormick,
*Multigrid methods for variational problems: general theory for the $V$-cycle*, SIAM J. Numer. Anal.**22**(1985), no. 4, 634–643. MR**795945**, DOI 10.1137/0722039 - F. A. Milner,
*Mixed finite element methods for quasilinear second-order elliptic problems*, Math. Comp.**44**(1985), no. 170, 303–320. MR**777266**, DOI 10.1090/S0025-5718-1985-0777266-1
J. Nečas, - P.-A. Raviart and J. M. Thomas,
*A mixed finite element method for 2nd order elliptic problems*, Mathematical aspects of finite element methods (Proc. Conf., Consiglio Naz. delle Ricerche (C.N.R.), Rome, 1975) Lecture Notes in Math., Vol. 606, Springer, Berlin, 1977, pp. 292–315. MR**0483555** - Frigyes Riesz and Béla Sz.-Nagy,
*Functional analysis*, Frederick Ungar Publishing Co., New York, 1955. Translated by Leo F. Boron. MR**0071727** - Elias M. Stein,
*Singular integrals and differentiability properties of functions*, Princeton Mathematical Series, No. 30, Princeton University Press, Princeton, N.J., 1970. MR**0290095** - Roger Temam,
*Navier-Stokes equations*, 3rd ed., Studies in Mathematics and its Applications, vol. 2, North-Holland Publishing Co., Amsterdam, 1984. Theory and numerical analysis; With an appendix by F. Thomasset. MR**769654** - R. Verfürth,
*A multilevel algorithm for mixed problems*, SIAM J. Numer. Anal.**21**(1984), no. 2, 264–271. MR**736330**, DOI 10.1137/0721019
J. Xu,

*Multi-grid methods and applications*, Springer-Verlag, New York, 1985. 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.

*An algebraic theory for multigrid methods for variational problems*, preprint.

*Les méthodes directes en théorie des équations elliptiques*, Academia, Prague, 1967.

*Theory of multilevel methods*, Thesis, Cornell University, Ithaca, NY, 1989. S. Zhang,

*Multi-level iterative techniques*, Thesis, Math. Res. Rep. 88020, Penn. State Univ., 1988.

## Additional Information

- © Copyright 1991 American Mathematical Society
- Journal: Math. Comp.
**56**(1991), 1-34 - MSC: Primary 65N22; Secondary 65N55
- DOI: https://doi.org/10.1090/S0025-5718-1991-1052086-4
- MathSciNet review: 1052086