×

Local Fourier analysis for multigrid with overlapping smoothers applied to systems of PDEs. (English) Zbl 1265.65256

Summary: Since their popularization in the late 1970s and early 1980s, multigrid methods have been a central tool in the numerical solution of the linear and nonlinear systems that arise from the discretization of many PDEs. In this paper, we present a local Fourier analysis (LFA, or local mode analysis) framework for analyzing the complementarity between relaxation and coarse-grid correction within multigrid solvers for systems of PDEs. Important features of this analysis framework include the treatment of arbitrary finite-element approximation subspaces, leading to discretization with staggered grids, and overlapping multiplicative Schwarz smoothers. The resulting tools are demonstrated for the Stokes, curl-curl, and grad-div equations.

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
35J25 Boundary value problems for second-order elliptic equations
35Q30 Navier-Stokes equations
35Q60 PDEs in connection with optics and electromagnetic theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bramble, Convergence estimates for multigrid algorithms without regularity assumptions, Mathematics of Computation 57 pp 23– (1991) · Zbl 0727.65101 · doi:10.1090/S0025-5718-1991-1079008-4
[2] Hackbusch, Convergence of multi-grid iterations applied to difference equations, Mathematics of Computation 34 pp 425– (1980) · Zbl 0422.65020
[3] McCormick, An algebraic interpretation of multigrid methods, SIAM Journal on Numerical Analysis 19 pp 548– (1982) · Zbl 0483.65061 · doi:10.1137/0719036
[4] Falgout, On two-grid convergence estimates, Numerical Linear Algebra with Applications 12 pp 471– (2005) · Zbl 1164.65343 · doi:10.1002/nla.437
[5] Brandt, Multi-level adaptive solutions to boundary-value problems, Mathematics of Computation 31 pp 333– (1977) · Zbl 0373.65054 · doi:10.1090/S0025-5718-1977-0431719-X
[6] Stüben, Lecture Notes in Mathematics, in: Multigrid Methods pp 1– (1982) · doi:10.1007/BFb0069928
[7] Yavneh, On red-black SOR smoothing in multigrid, SIAM Journal on Scientific Computing 17 (1) pp 180– (1996) · Zbl 0845.65013 · doi:10.1137/0917013
[8] Wienands, Numerical Insights (2005)
[9] bin Zubair, Multigrid for high-dimensional elliptic partial differential equations on non-equidistant grids, SIAM Journal on Scientific Computing 29 (4) pp 1613– (2007) · Zbl 1145.65109 · doi:10.1137/060665695
[10] Wienands, Fourier analysis of GMRES(m) preconditioned by multigrid, SIAM Journal on Scientific Computing 22 (2) pp 582– (2000) · Zbl 0967.65101 · doi:10.1137/S1064827599353014
[11] Gaspar, Fourier analysis for multigrid methods on triangular grids, SIAM Journal on Scientific Computing 31 (3) pp 2081– (2009) · Zbl 1190.65181 · doi:10.1137/080713483
[12] Zhou, Fourier analysis of multigrid methods on hexagonal grids, SIAM Journal on Scientific Computing 31 (2) pp 1518– (2009) · Zbl 1189.65296 · doi:10.1137/070709566
[13] Borzì, High-order discretization and multigrid solution of elliptic nonlinear constrained optimal control problems, Journal of Computational and Applied Mathematics 200 (1) pp 67– (2007) · Zbl 1107.65053 · doi:10.1016/j.cam.2005.12.023
[14] Hemker, Fourier two-level analysis for discontinuous Galerkin discretization with linear elements, Numerical Linear Algebra with Applications 11 (5-6) pp 473– (2004) · Zbl 1164.65498 · doi:10.1002/nla.356
[15] Arnold, Multigrid in H(div) and H(curl), Numerische Mathematik 85 (2) pp 197– (2000) · Zbl 0974.65113 · doi:10.1007/PL00005386
[16] Vanka, Block-implicit multigrid solution of Navier-Stokes equations in primitive variables, Journal of Computational Physics 65 pp 138– (1986) · Zbl 0606.76035 · doi:10.1016/0021-9991(86)90008-2
[17] John, Higher-order finite element discretizations in a benchmark problem for incompressible flows, International Journal for Numerical Methods in Fluids 37 (8) pp 885– (2001) · Zbl 1007.76040 · doi:10.1002/fld.195
[18] Boonen, Local Fourier analysis of multigrid for the curl-curl equation, SIAM Journal on Scientific Computing 30 (4) pp 1730– (2008) · Zbl 1168.65422 · doi:10.1137/070679119
[19] Schöberl, On Schwarz-type smoothers for saddle point problems, Numerische Mathematik 95 (2) pp 377– (2003) · Zbl 1033.65105 · doi:10.1007/s00211-002-0448-3
[20] Sivaloganathan, The use of local mode analysis in the design and comparison of multigrid methods, Computer Physics Communications 65 pp 246– (1991) · Zbl 0900.65076 · doi:10.1016/0010-4655(91)90178-N
[21] Molenaar, International Series of Numerical Mathematics, in: Multigrid Methods III pp 313– (1991) · doi:10.1007/978-3-0348-5712-3_23
[22] Manservisi, Numerical analysis of Vanka-type solvers for steady Stokes and Navier-Stokes flows, SIAM Journal on Numerical Analysis 44 (5) pp 2025– (2006) · Zbl 1120.76042 · doi:10.1137/060655407
[23] Larin, A comparative study of efficient iterative solvers for generalized Stokes equations, Numerical Linear Algebra with Applications 15 (1) pp 13– (2008) · Zbl 1212.65493 · doi:10.1002/nla.561
[24] Braess, Finite Elements (2001)
[25] Brenner, Texts in Applied Mathematics, in: The Mathematical Theory of Finite Element Methods (1994) · Zbl 0804.65101 · doi:10.1007/978-1-4757-4338-8
[26] Brandt, Multigrid Techniques: 1984 Guide with Applications to Fluid Dynamics (1984)
[27] Trottenberg, Multigrid (2001)
[28] Hiptmair, Multigrid method for H(div) in three dimensions, Electronic Transactions on Numerical Analysis 6 pp 133– (1997) · Zbl 0897.65046
[29] Gaspar, Distributive smoothers in multigrid for problems with dominating grad-div operators, Numerical Linear Algebra with Applications 15 (8) pp 661– (2008) · Zbl 1212.65484 · doi:10.1002/nla.587
[30] Bochev, An improved algebraic multigrid method for solving Maxwell’s equations, SIAM Journal on Scientific Computing 25 (2) pp 623– (2003) · Zbl 1163.76337 · doi:10.1137/S1064827502407706
[31] Hu, Toward an h-independent algebraic multigrid method for Maxwell’s equations, SIAM Journal on Scientific Computing 27 (5) pp 1669– (2006) · Zbl 1136.76341 · doi:10.1137/040608118
[32] Reitzinger, An algebraic multigrid method for finite element discretizations with edge elements, Numerical Linear Algebra with Applications 9 (3) pp 223– (2002) · Zbl 1071.65170 · doi:10.1002/nla.271
[33] Hiptmair, Multigrid method for Maxwell’s equations, SIAM Journal on Numerical Analysis 36 (1) pp 204– (1999) · Zbl 0922.65081 · doi:10.1137/S0036142997326203
[34] Raviart, Lecture Notes in Mathematics, in: Mathematical Aspects of Finite Element Methods pp 292– (1977) · doi:10.1007/BFb0064470
[35] Nédélec, Mixed finite elements in R3, Numerische Mathematik 35 (3) pp 315– (1980) · Zbl 0419.65069 · doi:10.1007/BF01396415
[36] Vassilevski, Multilevel iterative methods for mixed finite element discretizations of elliptic problems, Numerische Mathematik 63 (4) pp 503– (1992) · Zbl 0797.65086 · doi:10.1007/BF01385872
[37] Arnold, Preconditioning in H(div) and applications, Mathematics of Computation 66 (219) pp 957– (1997) · Zbl 0870.65112 · doi:10.1090/S0025-5718-97-00826-0
[38] Hiptmair, Multilevel methods for mixed finite elements in three dimensions, Numerische Mathematik 82 (2) pp 253– (1999) · Zbl 0929.65124 · doi:10.1007/s002110050419
[39] Brezzi, Springer Series in Computational Mathematics, in: Mixed and Hybrid Finite Element Methods (1991) · Zbl 0788.73002 · doi:10.1007/978-1-4612-3172-1
[40] Fortin, Old and new finite elements for incompressible flows, International Journal for Numerical Methods in Fluids 1 (4) pp 347– (1981) · Zbl 0467.76030 · doi:10.1002/fld.1650010406
[41] Girault, Lecture Notes in Mathematics, in: Finite Element Approximation of the Navier-Stokes Equations (1979) · Zbl 0413.65081 · doi:10.1007/BFb0063447
[42] Brandt, Numerical Methods for Partial Differential Equations pp 53– (1979) · doi:10.1016/B978-0-12-546050-7.50008-3
[43] Braess, An efficient smoother for the Stokes problem, Applied Numerical Mathematics 23 pp 3– (1997) · Zbl 0874.65095 · doi:10.1016/S0168-9274(96)00059-1
[44] John, Numerical performance of smoothers in coupled multigrid methods for the parallel solution of the incompressible Navier-Stokes equations, International Journal for Numerical Methods in Fluids 33 (4) pp 453– (2000) · Zbl 0979.76047 · doi:10.1002/1097-0363(20000630)33:4<453::AID-FLD15>3.0.CO;2-0
[45] Wobker, Numerical studies of Vanka-type smoothers in computational solid mechanics, Advances in Applied Mathematics and Mechanics 1 pp 29– (2009)
[46] Oppenheim, Prentice-Hall Signal Processing Series, in: Discrete-time Signal Processing (1999)
[47] Wittum, On the robustness of ILU-smoothing, SIAM Journal on Scientific Computing 10 pp 699– (1989) · Zbl 0677.65096 · doi:10.1137/0910043
[48] Brezina, Algebraic multigrid based on element interpolation (AMGe), SIAM Journal on Scientific Computing 22 pp 1570– (2000) · Zbl 0991.65133 · doi:10.1137/S1064827598344303
[49] Vassilevski, Sparse matrix element topology with application to AMG(e) and preconditioning, Numerical Linear Algebra with Applications 9 (6-7) pp 429– (2002) · Zbl 1071.65538 · doi:10.1002/nla.300
[50] Chartier, Lecture Notes in Computational Science and Engineering, in: Domain Decomposition Methods in Science and Engineering XVI pp 513– (2007) · doi:10.1007/978-3-540-34469-8_64
[51] Kolev, AMG by element agglomeration and constrained energy minimization interpolation, Numerical Linear Algebra with Applications 13 (9) pp 771– (2006) · Zbl 1174.65546 · doi:10.1002/nla.494
[52] Niestegge, Analysis of a multigrid Stokes solver, Applied Mathematics and Computation 35 (3) pp 291– (1990) · Zbl 0703.65075 · doi:10.1016/0096-3003(90)90048-8
[53] Elman, Numerical Mathematics and Scientific Computation (2005)
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.