## 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 PDF
- Math. Comp.
**83**(2014), 1083-1120 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**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 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**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 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

## Additional Information

**Blanca Ayuso de Dios**- Affiliation: Centre de Recerca Matematica, Campus de Bellaterra, Bellaterra, 08193, Spain
- Address at time of publication: Center for Uncertainty Quantification in Computational Science & Engineering, Computer, Electrical and Mathematical Sciences & Engineering Division (CEMSE), King Abdullah University of Science and Technology, Thuwal 23955-6900, Kingdom of Saudi Arabia
- Email: bayuso@crm.cat
**Michael Holst**- Affiliation: Department of Mathematics, University of California, San Diego, La Jolla, California 92093
- MR Author ID: 358602
- Email: mholst@math.ucsd.edu
**Yunrong Zhu**- Affiliation: Department of Mathematics, University of California, San Diego, La Jolla, California 92093
- Address at time of publication: Department of Mathematics, Idaho State University, Pocatello, Idaho 83209-8085
- Email: zhuyunr@isu.edu
**Ludmil Zikatanov**- Affiliation: Department of Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802
- Email: ltz@math.psu.edu
- Received by editor(s): January 14, 2011
- Received by editor(s) in revised form: February 1, 2012, June 15, 2012, and October 19, 2012
- Published electronically: October 30, 2013
- © Copyright 2013 American Mathematical Society
- Journal: Math. Comp.
**83**(2014), 1083-1120 - MSC (2010): Primary 65N30, 65N55
- DOI: https://doi.org/10.1090/S0025-5718-2013-02760-3
- MathSciNet review: 3167451