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
HTML articles powered by AMS MathViewer

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

Math. Comp. 83 (2014), 1083-1120

DOI: https://doi.org/10.1090/S0025-5718-2013-02760-3

Published electronically: October 30, 2013

PDF | Request permission

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.

References

Shmuel Agmon, Lectures on elliptic boundary value problems, Van Nostrand Mathematical Studies, No. 2, D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto-London, 1965. Prepared for publication by B. Frank Jones, Jr. with the assistance of George W. Batten, Jr. MR 178246
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, DOI 10.1051/m2an:2007006
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, DOI 10.1051/m2an:2008012
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
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, DOI 10.1137/S0036142901384162
Owe Axelsson, Iterative solution methods, Cambridge University Press, Cambridge, 1994. MR 1276069, DOI 10.1017/CBO9780511624100
Owe Axelsson, Iteration number for the conjugate gradient method, Math. Comput. Simulation 61 (2003), no. 3-6, 421–435. MODELLING 2001 (Pilsen). MR 1984142, DOI 10.1016/S0378-4754(02)00097-6
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.
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.
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, DOI 10.1007/s10915-009-9293-1
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, DOI 10.1007/s10915-010-9419-5
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, DOI 10.1090/S0025-5718-1989-0970699-3
James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1–22. MR 1023042, DOI 10.1090/S0025-5718-1990-1023042-6
James H. Bramble and Jinchao Xu, Some estimates for a weighted $L^2$ projection, Math. Comp. 56 (1991), no. 194, 463–476. MR 1066830, DOI 10.1090/S0025-5718-1991-1066830-3
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.
Susanne C. Brenner, Poincaré-Friedrichs inequalities for piecewise $H^1$ functions, SIAM J. Numer. Anal. 41 (2003), no. 1, 306–324. MR 1974504, DOI 10.1137/S0036142902401311
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, DOI 10.1002/nla.630
Susanne C. Brenner and Luke Owens, A $W$-cycle algorithm for a weakly over-penalized interior penalty method, Comput. Methods Appl. Mech. Engrg. 196 (2007), no. 37-40, 3823–3832. MR 2340007, DOI 10.1016/j.cma.2007.02.011
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
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, DOI 10.1002/anac.200410019
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, DOI 10.1016/j.cma.2005.06.015
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, DOI 10.1137/07069691X
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
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, DOI 10.1137/070685105
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, DOI 10.1137/050634736
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.
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
Philippe G. Ciarlet, The finite element method for elliptic problems, Studies in Mathematics and its Applications, Vol. 4, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. MR 520174
B. Cockburn, O. Dubois, J. Gopalakrishnan, and S. Tan. Multigrid for an HDG method. Submitted, 2010.
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, DOI 10.1137/060676106
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, DOI 10.1002/nla.504
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, DOI 10.1080/01630569908816904
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, DOI 10.2478/cmam-2003-0007
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, DOI 10.1016/j.jco.2007.02.003
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, DOI 10.1002/num.20678
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.
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, DOI 10.1137/0731086
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, DOI 10.1002/cpa.3160480203
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, DOI 10.1137/S0036142900378480
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, DOI 10.1137/090751190
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.
J. Gopalakrishnan and G. Kanschat, A multilevel discontinuous Galerkin method, Numer. Math. 95 (2003), no. 3, 527–550. MR 2012931, DOI 10.1007/s002110200392
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, DOI 10.1137/S1064827596305593
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, DOI 10.1007/s002110050115
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, DOI 10.1007/978-1-4612-4288-8
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, DOI 10.1137/S0036142901388081
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, DOI 10.1007/b138136
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, DOI 10.1002/nla.544
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, DOI 10.1137/060667372
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, DOI 10.1090/S0025-5718-96-00757-0
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, DOI 10.1007/978-3-322-91215-2
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, DOI 10.1007/978-3-642-11304-8_{2}1
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, DOI 10.1007/978-3-642-11304-8_{2}1
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, DOI 10.1137/080728457
Marcus Sarkis, Multilevel methods for $P_1$ 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, DOI 10.1090/conm/180/01963
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, DOI 10.1007/s002110050292
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, DOI 10.1137/110821639
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.
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, DOI 10.1090/S0025-5718-1990-1011446-7
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
Panayot S. Vassilevski, Multilevel block factorization preconditioners, Springer, New York, 2008. Matrix-based analysis and algorithms for solving finite element equations. MR 2427040
Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581–613. MR 1193013, DOI 10.1137/1034116
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, DOI 10.1142/S0218202508002619
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, DOI 10.1090/S0894-0347-02-00398-3
Jinchao Xu and Jun Zou, Some nonoverlapping domain decomposition methods, SIAM Rev. 40 (1998), no. 4, 857–914. MR 1659681, DOI 10.1137/S0036144596306800
Yunrong Zhu, Domain decomposition preconditioners for elliptic equations with jump coefficients, Numer. Linear Algebra Appl. 15 (2008), no. 2-3, 271–289. MR 2397305, DOI 10.1002/nla.566
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.
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, DOI 10.1002/nla.556