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.

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 0178246
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 https://doi.org/10.1051/m2an%3A2007006
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 https://doi.org/10.1051/m2an%3A2008012
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 https://doi.org/10.1137/S0036142901384162
Owe Axelsson, Iterative solution methods, Cambridge University Press, Cambridge, 1994. MR 1276069
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 https://doi.org/10.1016/S0378-4754%2802%2900097-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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1978. Studies in Mathematics and its Applications, Vol. 4. MR 0520174

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 https://doi.org/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 https://doi.org/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 https://doi.org/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

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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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

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 https://doi.org/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

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 https://doi.org/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 https://doi.org/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 https://doi.org/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

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 https://doi.org/10.1007/978-3-642-11304-8_21

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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1002/nla.556