×

Uniform convergence of multigrid V-cycle on adaptively refined finite element meshes for second order elliptic problems. (English) Zbl 1112.65104

Multigrid methods are not optimal if the smoothing operation is performed on the whole domain although local refinements occur only on a part of it. Therefore convergence proofs via space decomposition methods have been developed in the 90’s, although they are more technical than proofs with a separation of smoothing and approximation properties. Here the theory with space decompositions is elaborated and numerical examples are presented.

MSC:

65N12 Stability and convergence of numerical methods for boundary value problems involving PDEs
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations

Software:

ALBERT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Babuška I, Rheinboldt C. Error estimates for adaptive finite element computations. SIAM J Numer Anal, 1978, 15: 736–754 · Zbl 0398.65069 · doi:10.1137/0715049
[2] Morin P, Nochetto R H, Siebert K G. Data oscillation and convergence of adaptive FEM. SIAM J Numer Anal, 2000, 38: 466–488 · Zbl 0970.65113 · doi:10.1137/S0036142999360044
[3] Chen Z, Dai S. On the efficiency of adaptive finite element methods for elliptic problems with discontinuous coefficients. SIAM J Sci Comput, 2002, 24: 443–462 · Zbl 1032.65119 · doi:10.1137/S1064827501383713
[4] Mitchell W F. Optimal multilevel iterative methods for adaptive grids. SIAM J Sci Stat Comput, 1992, 13: 146–167 · Zbl 0746.65087 · doi:10.1137/0913009
[5] Bank R E, Dupont T F, Yserentant H. The hierarchical basis multigrid method. Numer Math, 1988, 52: 427–458 · Zbl 0645.65074 · doi:10.1007/BF01462238
[6] Bänsch E. Local mesh refinement in 2 and 3 dimensions. Impact of Computing in Science and Engineering, 1991, 3: 181–191 · Zbl 0744.65074 · doi:10.1016/0899-8248(91)90006-G
[7] Rivara M C. Algorithms for refining triangular grids suitable for adaptive and multigrid techniques. J Numer Meth Engrg, 1984, 20: 745–756 · Zbl 0536.65085 · doi:10.1002/nme.1620200412
[8] Stals L. Implementation of multigrid on parallel machines using adaptive finite element methods. Bjorstad P E, Espedal M S, Keyes D E, eds. In: Ninth International Conference on Domain Decomposition Methods. Bergen: DDM Org, 1997, 488–496
[9] Chen Z, Dai S. Adaptive Galerkin methods with error control for a dynamical Ginzburg-Landau model in superconductivity. SIAM J Numer Anal, 2001, 38: 1961–1985 · Zbl 0987.65096 · doi:10.1137/S0036142998349102
[10] Chen Z, Jia F. An adaptive finite element algorithm with reliable and efficient error control for linear parabolic problems. Math Comp, 2004, 73: 1163–1197 · Zbl 1052.65091 · doi:10.1090/S0025-5718-04-01634-5
[11] Chen Z, Nochetto R H, Schmidt A. A characteristic Galerkin method with adaptive error control for continuous casting problem. Comput Methods Appl Mech Engrg, 2000, 189: 249–276 · Zbl 0960.76045 · doi:10.1016/S0045-7825(99)00295-9
[12] Chen Z, Wu H. An adaptive finite element method with perfectly matched absorbing layers for the wave scattering by periodic structures. SIAM J Numer Anal, 2003, 41: 799–826 · Zbl 1049.78018 · doi:10.1137/S0036142902400901
[13] Schmidt A, Siebert K G. ALBERT: An adaptive hierarchical finite element toolbox. IAM, University of Freiburg. 2000, http://www.mathematik.uni-freiburg.de/IAM/Research/projectsdz/albert .
[14] Bramble J H, Ewing R E, Pasciak J E, et al. A preconditioneding technique for the efficient solution of problems with local grid refinement. Comput Methods Appl Mech Engrg, 1988, 67: 149–159 · Zbl 0619.76113 · doi:10.1016/0045-7825(88)90122-3
[15] McCormick S. Fast adaptive composite grid (FAC) methods. Böhmer K, Stetter H J, eds. In: Defect Correction Methods: Theory and Applications, Computing Supplementum 5. Wien: Sringer-Verlag, 1984, 115–121
[16] McCormick S, Thomas J. The fast adaptive composite grid (FAC) method for elliptic equations. Math Comp, 1986, 46: 439–456 · Zbl 0594.65078 · doi:10.1090/S0025-5718-1986-0829618-X
[17] Widlund O B. Optimal iterative refinement methods. In: Chan T, Glowinski R, Périaux J, Widlund O, eds. Domain Decomposition Methods. Philadelphia: SIAM, 1989, 114–125
[18] Bai D, Brandt A. Local mesh refinement multilevel techniques. SIAM J Sci Stat Comput, 1987, 8: 109–134 · Zbl 0619.65091 · doi:10.1137/0908025
[19] Bramble J H, Pasicak J E. New estimates for multigrid algorithms including the V-cycle. Math Comp, 1993, 60: 447–471 · Zbl 0783.65081
[20] Bramble J H, Pasicak J E, Wang J, et al. Convergence estimates for product iterative methods with applications to domain decomposition. Math Comp, 1991, 57: 23–45 · doi:10.1090/S0025-5718-1991-1079008-4
[21] Oswald P. Multilevel Finite Element Approximation, Theory and Applications. Stuttgart: Teubner Verlag, 1994 · Zbl 0830.65107
[22] Xu J. An introduction to multigrid convergence theory. In: Chan R, Chan T, Golub G, eds. Iterative Methods in Scientific Computing. Singapore: Springer-Verlag, 1997 · Zbl 0938.65142
[23] Ainsworth M, Mclean W. Multilevel diagonal scaling preconditioners for boundary element equations on locally refined meshes. Numer Math, 2003, 93: 387–413 · Zbl 1073.65132 · doi:10.1007/s002110100391
[24] Aksoylu B, Holst M. An odyssey into local refinement and multilevel preconditioning I: Optimality of the BPX preconditioned, Institute for Computational Engineering and Sciences, The University of Texas at Austin, ICES Technical Report 05-03, 2005
[25] Dahmen W, Kunoth A. Multilevel preconditioning. Numer Math, 1992, 63: 315–344 · Zbl 0757.65031 · doi:10.1007/BF01385864
[26] Oswald P. Multilevel solvers for elliptic problems on domains. In: Dahmen W, Kurdila A J, Oswald P, eds. Multiscale Wavelet Methods for PDEs. New York: Academic Press, 1996, 3–58
[27] Bank R E, Dupont T. An optimal order process for solving elliptic finite element equations. Math Comp, 1981, 36: 35–51 · Zbl 0466.65059 · doi:10.1090/S0025-5718-1981-0595040-2
[28] Bastian P, Wittum G. On robust and adaptive multigrid methods. In: Hemker P W, Wesseling P, eds. Multigrid Methods IV, Proceedings of the Fourth European Multigrid Conference, Amsterdam, July 6–9, 1993. Basel: Birkhäuser, 1994, 1–17 · Zbl 0814.65114
[29] Bornemann F A, Yserentant H. A basic norm equivalence for the theory of multilevel methods. Numer Math, 1993, 64: 455–476 · Zbl 0796.65135 · doi:10.1007/BF01388699
[30] Brandt A. Multilevel adaptive finite element methods I: Variational problems. In: Frehes J, Pallaschke D, Trotenberg U, eds. Special Topics of Applied Mathematics. Amsterdam: North-Holland, 1979, 91–128
[31] Griebel M, Oswald P. On the abstract theory of additive and multiplicative Schwarz algorithms. Numer Math, 1995, 70: 163–180 · Zbl 0826.65098 · doi:10.1007/s002110050115
[32] Rüde U. Mathematical and Computational Techniques for Multilevel Adaptive Method, Frontiers in Applied Mathematics 13. Philadelphia: SIAM, 1993 · Zbl 0857.65127
[33] Yserentant H. Old and new convergence proofs for multigrid methods. Acta Numerica, 1993, 3: 285–326 · Zbl 0788.65108 · doi:10.1017/S0962492900002385
[34] Xu J. Iterative methods by space decomposition and subspace correction. SIAM Review, 1992, 34: 581–613 · Zbl 0788.65037 · doi:10.1137/1034116
[35] Xu J, Zikatanov L. The method of alternating projections and the method of subspace corrections in Hilbert space. J Amer Math Soc, 2002, 15: 573–597 · Zbl 0999.47015 · doi:10.1090/S0894-0347-02-00398-3
[36] Bramble J H. Multigrid Methods, Pitman Research Notes in Mathematical Sciences 294. Essex: Longman, 1993
[37] Scott L R, Zhang S. Finite element interpolation of nonsmooth functions satisfying boundary conditions. Math Comp, 1990, 54: 483–493 · Zbl 0696.65007 · doi:10.1090/S0025-5718-1990-1011446-7
[38] Xu J. Multigrid convergence theory, Lecture Notes of the 2001 summer program on Multigrid Methods and Computational Electromagnetics in the Morningside Center of Mathematics. Chinese Academy of Sciences, Beijing, China
[39] Wu H. Uniform Convergence of a multigrid V-cycle for adaptive linear finite element methods, Postdoctoral Report. Institute of Computational Mathematics, Chinese Academy of Sciences, Beijing, 2002
[40] Brandt A. Multigrid Techniques: 1984 Guide, with applications to fluid dynamics, monograph. Weizmann Institute of Science, Rehovot, Israel, 1984 · Zbl 0581.76033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.