Multilevel preconditioners for discontinuous, Galerkin approximations of elliptic problems, with jump coefficients

Ayuso de Dios, Blanca; Holst, Michael; Zhu, Yunrong; Zikatanov, Ludmil

doi:10.1090/S0025-5718-2013-02760-3

Multilevel preconditioners for discontinuous, Galerkin approximations of elliptic problems, with jump coefficients

Authors: Blanca Ayuso de Dios, Michael Holst, Yunrong Zhu and Ludmil Zikatanov
Journal: Math. Comp. 83 (2014), 1083-1120
MSC (2010): Primary 65N30, 65N55
DOI: https://doi.org/10.1090/S0025-5718-2013-02760-3
Published electronically: October 30, 2013
MathSciNet review: 3167451
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce and analyze two-level and multilevel preconditioners for a family of Interior Penalty (IP) discontinuous Galerkin (DG) discretizations of second order elliptic problems with large jumps in the diffusion coefficient. Our approach to IPDG-type methods is based on a splitting of the DG space into two components that are orthogonal in the energy inner product naturally induced by the methods. As a result, the methods and their analysis depend in a crucial way on the diffusion coefficient of the problem. The analysis of the proposed preconditioners is presented for both symmetric and non-symmetric IP schemes; dealing simultaneously with the jump in the diffusion coefficient and the non-nested character of the relevant discrete spaces presents additional difficulties in the analysis, which precludes a simple extension of existing results. However, we are able to establish robustness (with respect to the diffusion coefficient) and near-optimality (up to a logarithmic term depending on the mesh size) for both two-level and BPX-type preconditioners, by using a more refined Conjugate Gradient theory. Useful by-products of the analysis are the supporting results on the construction and analysis of simple, efficient and robust two-level and multilevel preconditioners for non-conforming Crouzeix-Raviart discretizations of elliptic problems with jump coefficients. Following the analysis, we present a sequence of detailed numerical results which verify the theory and illustrate the performance of the methods.

[1] Shmuel Agmon, Lectures on elliptic boundary value problems, Prepared for publication by B. Frank Jones, Jr. with the assistance of George W. Batten, Jr. Van Nostrand Mathematical Studies, No. 2, D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto-London, 1965. MR 0178246
[2] Paola F. Antonietti and Blanca Ayuso, Schwarz domain decomposition preconditioners for discontinuous Galerkin approximations of elliptic problems: non-overlapping case, M2AN Math. Model. Numer. Anal. 41 (2007), no. 1, 21–54. MR 2323689, https://doi.org/10.1051/m2an:2007006
[3] Paola F. Antonietti and Blanca Ayuso, Multiplicative Schwarz methods for discontinuous Galerkin approximations of elliptic problems, M2AN Math. Model. Numer. Anal. 42 (2008), no. 3, 443–469. MR 2423794, https://doi.org/10.1051/m2an:2008012
[4] Paola F. Antonietti and Blanca Ayuso, Two-level Schwarz preconditioners for super penalty discontinuous Galerkin methods, Commun. Comput. Phys. 5 (2009), no. 2-4, 398–412. MR 2513693
[5] Douglas N. Arnold, Franco Brezzi, Bernardo Cockburn, and L. Donatella Marini, Unified analysis of discontinuous Galerkin methods for elliptic problems, SIAM J. Numer. Anal. 39 (2001/02), no. 5, 1749–1779. MR 1885715, https://doi.org/10.1137/S0036142901384162
[6] Owe Axelsson, Iterative solution methods, Cambridge University Press, Cambridge, 1994. MR 1276069
[7] Owe Axelsson, Iteration number for the conjugate gradient method, Math. Comput. Simulation 61 (2003), no. 3-6, 421–435. MODELLING 2001 (Pilsen). MR 1984142, https://doi.org/10.1016/S0378-4754(02)00097-6
[8] B. Ayuso de Dios, F. Brezzi, O. Havle, and L. D. Marini.
${L}^{2}$ -estimates for the DG IIPG-0 scheme.
Numer. Methods Partial Differential Equations, 28(5):1440-1465, 2012.
[9] B. Ayuso de Dios, M. Holst, Y. Zhu, and L. Zikatanov.
Multilevel preconditioners for discontinuous Galerkin approximations of elliptic problems with jump coefficients.
Arxiv preprint arXiv:1012.1287, 2010.
[10] Blanca Ayuso de Dios and Ludmil Zikatanov, Uniformly convergent iterative methods for discontinuous Galerkin discretizations, J. Sci. Comput. 40 (2009), no. 1-3, 4–36. MR 2511726, https://doi.org/10.1007/s10915-009-9293-1
[11] A. T. Barker, S. C. Brenner, E.-H. Park, and L.-Y. Sung, Two-level additive Schwarz preconditioners for a weakly over-penalized symmetric interior penalty method, J. Sci. Comput. 47 (2011), no. 1, 27–49. MR 2781147, https://doi.org/10.1007/s10915-010-9419-5
[12] James H. Bramble, Joseph E. Pasciak, and Alfred H. Schatz, The construction of preconditioners for elliptic problems by substructuring. IV, Math. Comp. 53 (1989), no. 187, 1–24. MR 970699, https://doi.org/10.1090/S0025-5718-1989-0970699-3
[13] James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1–22. MR 1023042, https://doi.org/10.1090/S0025-5718-1990-1023042-6
[14] James H. Bramble and Jinchao Xu, Some estimates for a weighted 𝐿² projection, Math. Comp. 56 (1991), no. 194, 463–476. MR 1066830, https://doi.org/10.1090/S0025-5718-1991-1066830-3
[15] A. Brandt, S. F. McCormick, and J. W. Ruge.
Algebraic multigrid (AMG) for automatic multigrid solution with application to geodetic computations.
Tech. Rep., Institute for Computational Studies, Colorado State University, 1982.
[16] Susanne C. Brenner, Poincaré-Friedrichs inequalities for piecewise 𝐻¹ functions, SIAM J. Numer. Anal. 41 (2003), no. 1, 306–324. MR 1974504, https://doi.org/10.1137/S0036142902401311
[17] S. C. Brenner, J. Cui, and L.-Y. Sung, Multigrid methods for the symmetric interior penalty method on graded meshes, Numer. Linear Algebra Appl. 16 (2009), no. 6, 481–501. MR 2522959, https://doi.org/10.1002/nla.630
[18] Susanne C. Brenner and Luke Owens, A 𝑊-cycle algorithm for a weakly over-penalized interior penalty method, Comput. Methods Appl. Mech. Engrg. 196 (2007), no. 37-40, 3823–3832. MR 2340007, https://doi.org/10.1016/j.cma.2007.02.011
[19] Susanne C. Brenner and Luke Owens, A weakly over-penalized non-symmetric interior penalty method, JNAIAM J. Numer. Anal. Ind. Appl. Math. 2 (2007), no. 1-2, 35–48. MR 2332345
[20] Susanne C. Brenner and Jie Zhao, Convergence of multigrid algorithms for interior penalty methods, Appl. Numer. Anal. Comput. Math. 2 (2005), no. 1, 3–18. MR 2157481, https://doi.org/10.1002/anac.200410019
[21] F. Brezzi, B. Cockburn, L. D. Marini, and E. Süli, Stabilization mechanisms in discontinuous Galerkin finite element methods, Comput. Methods Appl. Mech. Engrg. 195 (2006), no. 25-28, 3293–3310. MR 2220920, https://doi.org/10.1016/j.cma.2005.06.015
[22] Kolja Brix, Martin Campos Pinto, and Wolfgang Dahmen, A multilevel preconditioner for the interior penalty discontinuous Galerkin method, SIAM J. Numer. Anal. 46 (2008), no. 5, 2742–2768. MR 2421055, https://doi.org/10.1137/07069691X
[23] Kolja Brix, Martin Campos Pinto, Wolfgang Dahmen, and Ralf Massjung, Multilevel preconditioners for the interior penalty discontinuous Galerkin method. II. Quantitative studies, Commun. Comput. Phys. 5 (2009), no. 2-4, 296–325. MR 2513688
[24] E. Burman and B. Stamm, Low order discontinuous Galerkin methods for second order elliptic problems, SIAM J. Numer. Anal. 47 (2008/09), no. 1, 508–533. MR 2475950, https://doi.org/10.1137/070685105
[25] Erik Burman and Paolo Zunino, A domain decomposition method based on weighted interior penalties for advection-diffusion-reaction problems, SIAM J. Numer. Anal. 44 (2006), no. 4, 1612–1638. MR 2257119, https://doi.org/10.1137/050634736
[26] L. Chen, M. Holst, J. Xu, and Y. Zhu.
Local multilevel preconditioners for elliptic equations with jump coefficients on bisection grids.
Arxiv preprint arXiv:1006.3277, 2010.
[27] Durkbin Cho, Jinchao Xu, and Ludmil Zikatanov, New estimates for the rate of convergence of the method of subspace corrections, Numer. Math. Theory Methods Appl. 1 (2008), no. 1, 44–56. MR 2401666
[28] Philippe G. Ciarlet, The finite element method for elliptic problems, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. Studies in Mathematics and its Applications, Vol. 4. MR 0520174
[29] B. Cockburn, O. Dubois, J. Gopalakrishnan, and S. Tan.
Multigrid for an HDG method.
Submitted, 2010.
[30] Daniele A. Di Pietro, Alexandre Ern, and Jean-Luc Guermond, Discontinuous Galerkin methods for anisotropic semidefinite diffusion with advection, SIAM J. Numer. Anal. 46 (2008), no. 2, 805–831. MR 2383212, https://doi.org/10.1137/060676106
[31] Veselin A. Dobrev, Raytcho D. Lazarov, Panayot S. Vassilevski, and Ludmil T. Zikatanov, Two-level preconditioning of discontinuous Galerkin approximations of second-order elliptic equations, Numer. Linear Algebra Appl. 13 (2006), no. 9, 753–770. MR 2269798, https://doi.org/10.1002/nla.504
[32] Vít Dolejší, Miloslav Feistauer, and Jiří Felcman, On the discrete Friedrichs inequality for nonconforming finite elements, Numer. Funct. Anal. Optim. 20 (1999), no. 5-6, 437–447. MR 1704954, https://doi.org/10.1080/01630569908816904
[33] Maksymilian Dryja, On discontinuous Galerkin methods for elliptic problems with discontinuous coefficients, Comput. Methods Appl. Math. 3 (2003), no. 1, 76–85. Dedicated to Raytcho Lazarov. MR 2002258
[34] Maksymilian Dryja, Juan Galvis, and Marcus Sarkis, BDDC methods for discontinuous Galerkin discretization of elliptic problems, J. Complexity 23 (2007), no. 4-6, 715–739. MR 2372024, https://doi.org/10.1016/j.jco.2007.02.003
[35] Maksymilian Dryja, Juan Galvis, and Marcus Sarkis, Neumann-Neumann methods for a DG discretization on geometrically nonconforming substructures, Numer. Methods Partial Differential Equations 28 (2012), no. 4, 1194–1226. MR 2914789, https://doi.org/10.1002/num.20678
[36] M. Dryja and M. Sarkis.
FETI-DP method for DG discretization of elliptic problems with discontinuous coefficients.
Technical report, Instituto de Matematica Pura e Aplicada, Brazil, 2010.
submitted.
[37] Maksymilian Dryja, Barry F. Smith, and Olof B. Widlund, Schwarz analysis of iterative substructuring algorithms for elliptic problems in three dimensions, SIAM J. Numer. Anal. 31 (1994), no. 6, 1662–1694. MR 1302680, https://doi.org/10.1137/0731086
[38] Maksymilian Dryja and Olof B. Widlund, Schwarz methods of Neumann-Neumann type for three-dimensional elliptic finite element problems, Comm. Pure Appl. Math. 48 (1995), no. 2, 121–155. MR 1319698, https://doi.org/10.1002/cpa.3160480203
[39] Xiaobing Feng and Ohannes A. Karakashian, Two-level additive Schwarz methods for a discontinuous Galerkin approximation of second order elliptic problems, SIAM J. Numer. Anal. 39 (2001), no. 4, 1343–1365. MR 1870847, https://doi.org/10.1137/S0036142900378480
[40] Juan Galvis and Yalchin Efendiev, Domain decomposition preconditioners for multiscale flows in high-contrast media, Multiscale Model. Simul. 8 (2010), no. 4, 1461–1483. MR 2718268, https://doi.org/10.1137/090751190
[41] G. H. Golub and C. F. Van Loan.
Matrix computations.
Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, third edition, 1996.
[42] J. Gopalakrishnan and G. Kanschat, A multilevel discontinuous Galerkin method, Numer. Math. 95 (2003), no. 3, 527–550. MR 2012931, https://doi.org/10.1007/s002110200392
[43] I. G. Graham and M. J. Hagger, Unstructured additive Schwarz-conjugate gradient method for elliptic problems with highly discontinuous coefficients, SIAM J. Sci. Comput. 20 (1999), no. 6, 2041–2066. MR 1703306, https://doi.org/10.1137/S1064827596305593
[44] M. Griebel and P. Oswald, On the abstract theory of additive and multiplicative Schwarz algorithms, Numer. Math. 70 (1995), no. 2, 163–180. MR 1324736, https://doi.org/10.1007/s002110050115
[45] Wolfgang Hackbusch, Iterative solution of large sparse systems of equations, Applied Mathematical Sciences, vol. 95, Springer-Verlag, New York, 1994. Translated and revised from the 1991 German original. MR 1247457
[46] Axel Klawonn, Olof B. Widlund, and Maksymilian Dryja, Dual-primal FETI methods for three-dimensional elliptic problems with heterogeneous coefficients, SIAM J. Numer. Anal. 40 (2002), no. 1, 159–179. MR 1921914, https://doi.org/10.1137/S0036142901388081
[47] Ralf Kornhuber, Ronald Hoppe, Jacques Périaux, Olivier Pironneau, Olof Widlund, and Jinchao Xu (eds.), Domain decomposition methods in science and engineering, Lecture Notes in Computational Science and Engineering, vol. 40, Springer-Verlag, Berlin, 2005. Papers from the 15th International Conference on Domain Decomposition held at the Freie Universität Berlin, Berlin, July 21–25, 2003. MR 2230692
[48] J. K. Kraus and S. K. Tomar, A multilevel method for discontinuous Galerkin approximation of three-dimensional anisotropic elliptic problems, Numer. Linear Algebra Appl. 15 (2008), no. 5, 417–438. MR 2423513, https://doi.org/10.1002/nla.544
[49] Johannes K. Kraus and Satyendra K. Tomar, Multilevel preconditioning of two-dimensional elliptic problems discretized by a class of discontinuous Galerkin methods, SIAM J. Sci. Comput. 30 (2008), no. 2, 684–706. MR 2385881, https://doi.org/10.1137/060667372
[50] Jan Mandel and Marian Brezina, Balancing domain decomposition for problems with large jumps in coefficients, Math. Comp. 65 (1996), no. 216, 1387–1401. MR 1351204, https://doi.org/10.1090/S0025-5718-96-00757-0
[51] Peter Oswald, Multilevel finite element approximation, Teubner Skripten zur Numerik. [Teubner Scripts on Numerical Mathematics], B. G. Teubner, Stuttgart, 1994. Theory and applications. MR 1312165
[52] Clemens Pechstein and Robert Scheichl, Weighted Poincaré inequalities and applications in domain decomposition, Domain decomposition methods in science and engineering XIX, Lect. Notes Comput. Sci. Eng., vol. 78, Springer, Heidelberg, 2011, pp. 197–204. MR 2867660, https://doi.org/10.1007/978-3-642-11304-8_21
[53] Clemens Pechstein and Robert Scheichl, Weighted Poincaré inequalities and applications in domain decomposition, Domain decomposition methods in science and engineering XIX, Lect. Notes Comput. Sci. Eng., vol. 78, Springer, Heidelberg, 2011, pp. 197–204. MR 2867660, https://doi.org/10.1007/978-3-642-11304-8_21
[54] F. Prill, M. Lukáčová-Medviďová, and R. Hartmann, Smoothed aggregation multigrid for the discontinuous Galerkin method, SIAM J. Sci. Comput. 31 (2009), no. 5, 3503–3528. MR 2538866, https://doi.org/10.1137/080728457
[55] Marcus Sarkis, Multilevel methods for 𝑃₁ nonconforming finite elements and discontinuous coefficients in three dimensions, Domain decomposition methods in scientific and engineering computing (University Park, PA, 1993) Contemp. Math., vol. 180, Amer. Math. Soc., Providence, RI, 1994, pp. 119–124. MR 1312384, https://doi.org/10.1090/conm/180/01963
[56] Marcus Sarkis, Nonstandard coarse spaces and Schwarz methods for elliptic problems with discontinuous coefficients using non-conforming elements, Numer. Math. 77 (1997), no. 3, 383–406. MR 1469678, https://doi.org/10.1007/s002110050292
[57] Robert Scheichl, Panayot S. Vassilevski, and Ludmil T. Zikatanov, Weak approximation properties of elliptic projections with functional constraints, Multiscale Model. Simul. 9 (2011), no. 4, 1677–1699. MR 2861254, https://doi.org/10.1137/110821639
[58] R. Scheichl, P. S. Vassilevski, and L. T. Zikatanov.
Multilevel methods for elliptic problems with highly varying coefficients on non-aligned coarse grids.
To appear in SINUM. Also available as Lawrence Livermore National Laboratory technical report LLNL-JRNL-404462, August 2010., 2012.
[59] L. Ridgway Scott and Shangyou Zhang, Finite element interpolation of nonsmooth functions satisfying boundary conditions, Math. Comp. 54 (1990), no. 190, 483–493. MR 1011446, https://doi.org/10.1090/S0025-5718-1990-1011446-7
[60] Rolf Stenberg, Mortaring by a method of J. A. Nitsche, Computational mechanics (Buenos Aires, 1998) Centro Internac. Métodos Numér. Ing., Barcelona, 1998, pp. CD-ROM file. MR 1839048
[61] Panayot S. Vassilevski, Multilevel block factorization preconditioners, Springer, New York, 2008. Matrix-based analysis and algorithms for solving finite element equations. MR 2427040
[62] Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, https://doi.org/10.1137/1034116
[63] Jinchao Xu and Yunrong Zhu, Uniform convergent multigrid methods for elliptic problems with strongly discontinuous coefficients, Math. Models Methods Appl. Sci. 18 (2008), no. 1, 77–105. MR 2378084, https://doi.org/10.1142/S0218202508002619
[64] Jinchao Xu and Ludmil Zikatanov, The method of alternating projections and the method of subspace corrections in Hilbert space, J. Amer. Math. Soc. 15 (2002), no. 3, 573–597. MR 1896233, https://doi.org/10.1090/S0894-0347-02-00398-3
[65] Jinchao Xu and Jun Zou, Some nonoverlapping domain decomposition methods, SIAM Rev. 40 (1998), no. 4, 857–914. MR 1659681, https://doi.org/10.1137/S0036144596306800
[66] Yunrong Zhu, Domain decomposition preconditioners for elliptic equations with jump coefficients, Numer. Linear Algebra Appl. 15 (2008), no. 2-3, 271–289. MR 2397305, https://doi.org/10.1002/nla.566
[67] Y. Zhu.
Analysis of a multigrid preconditioner for Crouzeix-Raviart discretization of elliptic partial differential equation with jump coefficients.
Numer. Linear Algebra Appl., DOI 10.1002/nla.1856, Also available on arXiv.org, arXiv:1110.5159, September 2012.
[68] Ludmil T. Zikatanov, Two-sided bounds on the convergence rate of two-level methods, Numer. Linear Algebra Appl. 15 (2008), no. 5, 439–454. MR 2423514, https://doi.org/10.1002/nla.556