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), 389414
MSC:
Primary 65N30; Secondary 65F10
MathSciNet review:
930228
Fulltext PDF Free Access
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 socalled 'symmetric' multigrid schemes. We show that for the variable cycle and the 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 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 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.
 [1]
Randolph
E. Bank, A comparison of two multilevel iterative methods for
nonsymmetric and indefinite elliptic finite element equations, SIAM J.
Numer. Anal. 18 (1981), no. 4, 724–743. MR 622706
(82f:65110), http://dx.doi.org/10.1137/0718048
 [2]
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
(86j:65037), http://dx.doi.org/10.1137/0722038
 [3]
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
(82b:65113), http://dx.doi.org/10.1090/S00255718198105950402
 [4]
D.
Braess and W.
Hackbusch, A new convergence proof for the multigrid method
including the 𝑉cycle, SIAM J. Numer. Anal.
20 (1983), no. 5, 967–975. MR 714691
(85h:65233), http://dx.doi.org/10.1137/0720066
 [5]
James
H. Bramble and Joseph
E. Pasciak, New convergence estimates for
multigrid algorithms, Math. Comp.
49 (1987), no. 180, 311–329. MR 906174
(89b:65234), http://dx.doi.org/10.1090/S0025571819870906174X
 [6]
Achi
Brandt, Multilevel adaptive solutions to
boundaryvalue problems, Math. Comp.
31 (1977), no. 138, 333–390. MR 0431719
(55 #4714), http://dx.doi.org/10.1090/S0025571819770431719X
 [7]
Pierre
Grisvard, Behavior of the solutions of an elliptic boundary value
problem in a polygonal or polyhedral domain, Sympos. (SYNSPADE),
Univ. Maryland, College Park, Md., 1975) Academic Press, New York, 1976,
pp. 207–274. MR 0466912
(57 #6786)
 [8]
W. Hackbusch, MultiGrid Methods and Applications, SpringerVerlag, New York, 1985.
 [9]
Tosio
Kato, Perturbation theory for linear operators, 2nd ed.,
SpringerVerlag, Berlin, 1976. Grundlehren der Mathematischen
Wissenschaften, Band 132. MR 0407617
(53 #11389)
 [10]
V.
A. Kondrat′ev, Boundary value problems for elliptic equations
in domains with conical or angular points, Trudy Moskov. Mat.
Obšč. 16 (1967), 209–292 (Russian). MR 0226187
(37 #1777)
 [11]
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
(33 #1719)
 [12]
J. L. Lions & E. Magenes, Problèmes aux Limites non Homogènes et Applications, Dunod, Paris, 1968.
 [13]
J.F.
Maitre and F.
Musy, Algebraic formalisation of the multigrid method in the
symmetric and positive definite case—a convergence estimation for the
𝑉cycle, Multigrid methods for integral and differential
equations (Bristol, 1983), Inst. Math. Appl. Conf. Ser. New Ser.,
vol. 3, Oxford Univ. Press, New York, 1985, pp. 213–223. MR 849375
(87i:65044)
 [14]
Jan
Mandel, Multigrid convergence for nonsymmetric, indefinite
variational problems and one smoothing step, Appl. Math. Comput.
19 (1986), no. 14, 201–216. Second Copper
Mountain conference on multigrid methods (Copper Mountain, Colo., 1985). MR 849837
(87i:65097), http://dx.doi.org/10.1016/00963003(86)901049
 [15]
Jan
Mandel, Algebraic study of multigrid methods for symmetric,
definite problems, Appl. Math. Comput. 25 (1988),
no. 1, 39–56. MR 923402
(89d:65036), http://dx.doi.org/10.1016/00963003(88)90063X
 [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. 21 (1984), no. 2,
255–263. MR
736329 (85h:65115), http://dx.doi.org/10.1137/0721018
 [18]
S.
F. McCormick, Multigrid methods for variational problems: general
theory for the 𝑉cycle, SIAM J. Numer. Anal.
22 (1985), no. 4, 634–643. MR 795945
(86m:65030), http://dx.doi.org/10.1137/0722039
 [19]
J. Neoas, Les Méthodes Directes en Théorie des Équations Elliptiques, Academia, Prague, 1967.
 [20]
Alfred
H. Schatz, An observation concerning
RitzGalerkin methods with indefinite bilinear forms, Math. Comp. 28 (1974), 959–962. MR 0373326
(51 #9526), http://dx.doi.org/10.1090/S00255718197403733260
 [21]
Harry
Yserentant, The convergence of multilevel methods
for solving finiteelement equations in the presence of
singularities, Math. Comp.
47 (1986), no. 176, 399–409. MR 856693
(88d:65149), http://dx.doi.org/10.1090/S00255718198608566939
 [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. 724743. 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. 617633. 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. 3551. MR 595040 (82b:65113)
 [4]
 D. Braess & W. Hackbusch, "A new convergence proof for the multigrid method including the Vcycle," SIAM J. Numer. Anal., v. 20, 1983, pp. 967975. MR 714691 (85h:65233)
 [5]
 J. H. Bramble & J. E. Pasciak, "New convergence estimates for multigrid algorithms," Math. Comp., v. 49, 1987, pp. 311329. MR 906174 (89b:65234)
 [6]
 A. Brandt, "Multilevel adaptive solutions to boundaryvalue problems," Math. Comp., v. 31, 1977, pp. 333390. 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. 207274. MR 0466912 (57:6786)
 [8]
 W. Hackbusch, MultiGrid Methods and Applications, SpringerVerlag, New York, 1985.
 [9]
 T. Kato, Perturbation Theory for Linear Operators, SpringerVerlag, 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. 227313. MR 0226187 (37:1777)
 [11]
 S. G. Krein & Y. I. Petunin, Scales of Banach spaces, Russian Math. Surveys, vol. 21, 1966, pp. 85160. 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 caseA convergence estimation for the Vcycle," 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. 201216. 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. 255263. MR 736329 (85h:65115)
 [18]
 S. F. McCormick, "Multigrid methods for variational problems: General theory for the Vcycle," SIAM J. Numer. Anal., v. 22, 1985, pp. 634643. 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 RitzGalerkin methods with indefinite bilinear forms," Math. Comp., v. 28, 1974, pp. 959962. MR 0373326 (51:9526)
 [21]
 H. Yserentant, "The convergence of multilevel methods for solving finiteelement equations in the presence of singularities," Math. Comp., v. 47, 1986, pp. 399409. 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
DOI:
http://dx.doi.org/10.1090/S00255718198809302286
PII:
S 00255718(1988)09302286
Article copyright:
© Copyright 1988 American Mathematical Society
