Mathematics of Computation

Convergence of the multigrid

-cycle algorithm for second-order boundary value problems without full elliptic regularity

Author(s): Susanne C. Brenner.
Journal: Math. Comp. 71 (2002), 507-525.
MSC (2000): Primary 65N55, 65N30
Posted: November 19, 2001
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract: The multigrid

-cycle algorithm using the Richardson relaxation scheme as the smoother is studied in this paper. For second-order elliptic boundary value problems, the contraction number of the

-cycle algorithm is shown to improve uniformly with the increase of the number of smoothing steps, without assuming full elliptic regularity. As a consequence, the

-cycle convergence result of Braess and Hackbusch is generalized to problems without full elliptic regularity.

1.: 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 86j:65037
2.: R.E. Bank and T.F. Dupont, An optimal order process for solving finite element equations, Math. Comp. 36 (1981), 35-51. MR 82b:65113
3.: C. Bennett and R. Sharpley, Interpolation of operators, Academic Press, Boston, 1988. MR 89e:46001
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 85h:65233
5.: J.H. Bramble, Multigrid Methods, Pitman Research Notes in Mathematics Series 294, Longman Scientific & Technical, New York, 1993. MR 95b:65002
6.: J.H. Bramble and S.R. Hilbert, Estimation of linear functionals on Sobolev spaces with application to Fourier transforms and spline interpolation, SIAM J. Numer. Anal. 7 (1970), 113-124. MR 41:7819
7.: J.H. Bramble and J.E. Pasciak, New convergence estimates for multigrid algorithms, Math. Comp. 49 (1987), 311-329. MR 89b:65234
8.: -, New estimates for multigrid algorithms including the V-cycle, Math. Comp. 60 (1993), 447-471. MR 94a:65064
9.: -, Uniform convergence estimates for multigrid -cycle algorithms with less than full elliptic regularity, Domain Decomposition Methods in Science and Engineering (Como, 1992), Contemp. Math. 157, Amer. Math. Soc., Providence, RI, 1994, pp. 17-26. MR 95f:65202
10.: J.H. Bramble and X. Zhang, The analysis of multigrid methods, Handb. Numer. Anal. VII, North-Holland, Amsterdam, 2000, 173-415. CMP 2001:08
11.: -, Uniform convergence of the multigrid -cycle for an anisotropic problem, Math. Comp. 70 (2001), 453-470.
12.: S.C. Brenner, Multigrid methods for the computation of singular solutions and stress intensity factors I: Corner singularities, Math. Comp. 68 (1999), 559-583. MR 99i:65138
13.: -, A nonstandard finite element interpolation estimate, Numer. Funct. Anal. Optim. 20 (1999), 245-250. MR 2000b:65210
14.: S.C. Brenner and L.R. Scott, The mathematical theory of finite element methods, Springer-Verlag, New York-Berlin-Heidelberg, 1994. MR 95f:65001
15.: S.C. Brenner and L.-Y. Sung, Multigrid methods for the computation of singular solutions and stress intensity factors II: Crack singularities, BIT 37 (1997), 623-643. MR 99i:65139
16.: P.-G. Ciarlet, The Finite Element Method for Elliptic Problems, North Holland, Amsterdam-New York-Oxford, 1978. MR 58:25001
17.: P. Clément, Approximation by finite element functions using local regularization, R.A.I.R.O. Sér. Rouge Anal. Numér. 9 (1975), 77-84. MR 53:4569
18.: M. Dauge, Elliptic boundary value problems on corner domains (Lecture Notes in Mathematics 1341), Springer-Verlag, Berlin-Heidelberg, 1988. MR 91a:35078
19.: T. Dupont and R. Scott, Polynomial approximation of functions in Sobolev spaces, Math. Comp. 34 (1980), 441-463. MR 81h:65014
20.: M. Griebel and P. Oswald, On the abstract theory of additive and multiplicative Schwarz algorithms, Numer. Math. 70 (1995), 163-180. MR 96a:65164
21.: P. Grisvard, Elliptic problems in nonsmooth domains, Pitman, Boston, 1985. MR 86m:35044
22.: W. Hackbusch, Multigrid convergence theory, Proceedings of the Conference Held at Köln-Porz, November 23-27, 1981 (W. Hackbusch and U. Trottenberg, eds.), Lecture Notes in Mathematics 960, Springer-Verlag, Berlin, 1982, pp. 177-219. MR 84k:65113
23.: -, Multigrid methods and applications, Springer-Verlag, Berlin, 1985. MR 87e:65082
24.: G.H. Hardy, J.E. Littlewood and G. Pólya, Inequalities, Cambridge University Press, Cambridge, 1934.
25.: J. Mandel, S. McCormick and R. Bank, Variational multigrid theory, Multigrid Methods (S.F. McCormick, ed.), Frontiers In Applied Mathematics 3, SIAM, Philadelphia, 1987, pp. 131-177. CMP 21:05
26.: S.F. McCormick, Multigrid methods for variational problems: further results, SIAM J. Numer. Anal. 21 (1984), 255-263. MR 85h:65115
27.: S.A. Nazarov and B.A. Plamenevsky, Elliptic problems in domains with piecewise smooth boundaries, Expositions in Mathematics 13, de Gruyter, Berlin-New York, 1994. MR 95h:35001
28.: N. Neuss, -cycle convergence with unsymmetric smoothers and applications to an anisotropic model problem, SIAM J. Numer. Anal. 35 (1998), 1201-1212.
29.: L.R. Scott and S. Zhang, Finite element interpolation of nonsmooth functions satisfying boundary conditions, Math. Comp. 54 (1990), 483-493. MR 90j:65021
30.: H. Triebel, Interpolation theory, function spaces, differential operators, North-Holland, Amsterdam, 1978. MR 80i:46032b
31.: J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Review 34 (1992), 581-613. MR 93k:65029
32.: H. Yserentant, Old and new convergence proofs for multigrid methods, Acta Numer. (1993), 285-326. MR 94i:65128
33.: X. Zhang, Multilevel Schwarz methods, Numer. Math. 63 (1992), 521-539. MR 93h:650247

Susanne C. Brenner
Affiliation: Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208
Email: brenner@math.sc.edu

DOI: 10.1090/S0025-5718-01-01361-8
PII: S 0025-5718(01)01361-8
Keywords: $V$-cycle multigrid algorithm, second-order boundary value problems without full elliptic regularity
Received by editor(s): August 18, 1999
Received by editor(s) in revised form: October 27, 1999 and July 10, 2000
Posted: November 19, 2001
Additional Notes: This work was supported in part by the National Science Foundation under Grant Nos. DMS-96-00133 and DMS-00-74246.
Copyright of article: Copyright 2001, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS