Optimal-order nonnested multigrid methods for solving finite element equations. I. On quasi-uniform meshes

Author:
Shangyou Zhang

Journal:
Math. Comp. **55** (1990), 23-36

MSC:
Primary 65N55; Secondary 65F10, 65N30

DOI:
https://doi.org/10.1090/S0025-5718-1990-1023054-2

MathSciNet review:
1023054

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that the multigrid method works with optimal computational order even when the multiple meshes are not nested. When a coarse mesh is not a submesh of the finer one, the coarse-level correction usually does not have the projection property and does amplify the iterative error in some components. Nevertheless, the low-frequency components of the error can still be caught by the coarse-level correction. Since the (amplified) high-frequency errors will be damped out by the fine-level smoothing efficiently, the optimal work order of the standard multigrid method can still be maintained. However, unlike the case of nested meshes, a nonnested multigrid method with one smoothing does not converge in general, no matter whether it is a *V*-cycle or a *W*-cycle method.

It is shown numerically that the convergence rates of nonnested multigrid methods are not necessarily worse than those of nested ones. Since nonnested multigrid methods accept quite arbitrarily related meshes, we may then combine the efficiencies of adaptive refinements and of multigrid algorithms.

**[1]**R. Bank and T. Dupont,*An optimal order process for solving finite element equations*, Math. Comp.**36**(1981), 35-51. MR**595040 (82b:65113)****[2]**J. H. Bramble, J. E. Pasciak, and J. Xu,*The Analysis of multigrid algorithms with nonnested spaces or non-inherited quadratic forms*(preprint).**[3]**S. C. Brenner,*An optimal-order multigrid method for**nonconforming finite elements*, Math. Comp.**52**(1989), 1-15. MR**946598 (89f:65119)****[4]**P. G. Ciarlet,*The finite element method for elliptic problems*, North-Holland, Amsterdam, New York, Oxford, 1978. MR**0520174 (58:25001)****[5]**P. Grisvard,*Elliptic problems in nonsmooth domains*, Pitman, 1985. MR**775683 (86m:35044)****[6]**W. Hackbusch and U. Trottenberg,*Multigrid methods*II, Lecture Notes in Math., vol. 1228, Springer-Verlag, Berlin and New York, 1986. MR**896053 (88b:65004)****[7]**-,*Multigrid methods*, Lecture Notes in Math., vol. 960, Springer-Verlag, Berlin and New York, 1982.**[8]**W. Hackbusch,*Multigrid methods and applications*, Springer, 1985. MR**814495 (87e:65082)****[9]**J. Mandel,*Multigrid convergence for nonsymmetric, indefinite variational problems and one smoothing step*, Appl. Math. Comput.**19**(1986), 201-216. MR**849837 (87i:65097)****[10]**S. F. McCormick,*Multigrid Methods*, Frontiers in Applied Mathematics, SIAM, Philadelphia, PA, 1987. MR**972752 (89m:65004)****[11]**P. Peisker,*A multilevel algorithm for the biharmonic problem*, Numer. Math.**46**(1985), 623-634. MR**796649 (86j:65144)****[12]**P. Peisker and D. Braess,*A conjugate gradient method and a multigrid algorithm for Morley's finite element approximation of the biharmonic equation*, Numer. Math.**50**(1987), 567-586. MR**880336 (88e:65147)****[13]**J. Pitkäranta and T. Saarinen,*A multigrid version of a simple finite element method for the Stokes problem*, Math. Comp.**45**(1985), 1-14. MR**790640 (86h:65168)****[14]**L. R. Scott and S. Zhang,*Finite element interpolation of nonsmooth functions satisfying boundary conditions*, Math. Comp.**54**(1990), (to appear). MR**1011446 (90j:65021)****[15]**-,*A nonnested multigrid method for three dimensional boundary value problems: An introduction to NMGTM code*, in preparation.**[16]**R. Verfürth,*A multilevel algorithm for mixed problems*, SIAM J. Numer. Anal.**21**(1984), 264-271. MR**736330 (85f:65112)****[17]**-,*A combined conjugate gradient-multigrid algorithm for the numerical solution of the Stokes problem*, IMA J. Numer. Anal.**4**(1984), 441-455. MR**768638 (86f:65200)****[18]**-,*Multilevel algorithms for mixed problems*. II.*Treatment of the mini-element*, SIAM J. Numer. Anal.**25**(1988), 285-293. MR**933725 (89a:65175)****[19]**S. Zhang,*Multi-level iterative techniques*, Ph. D. thesis, Pennsylvania State University, 1988.**[20]**-,*Successive subdivisions of tetrahedra and multigrid methods on tetrahedral meshes*, submitted, also in [19].**[21]**-,*Multigrid methods for solving biharmonic*,*finite element equations*, Numer. Math.**56**(1989), 613-624.**[22]**-,*An optimal order interpolation operator from**to piecewise linear functions**on polygons*, §6.3 in [19].**[23]**-,*Optimal-order nonnested multigrid methods for solving finite element equations*II:*Non-quasiuniform meshes*, Math. Comp.**55**(1990), (to appear). MR**1023054 (91g:65268)**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1990-1023054-2

Article copyright:
© Copyright 1990
American Mathematical Society