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.
- 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
- 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
Retrieve articles in Mathematics of Computation with MSC (2010): 65N30, 65N55
Retrieve articles in all journals with MSC (2010): 65N30, 65N55
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
Keywords:
Multilevel preconditioner,
discontinuous Galerkin methods,
Crouzeix-Raviart finite elements,
space decomposition
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
Article copyright:
© Copyright 2013
American Mathematical Society