Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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

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 [Enhancements On Off] (What's this?)

  • [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 (31 #2504)
  • [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 (2008b:65140), 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 (2009f:65243), 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 (2010d:65310)
  • [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 (2002k:65183), https://doi.org/10.1137/S0036142901384162
  • [6] Owe Axelsson, Iterative solution methods, Cambridge University Press, Cambridge, 1994. MR 1276069 (95f:65005)
  • [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 (2004g:65031), 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 (2010d:65311), 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 (2012f:65184), 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 (89m:65098), https://doi.org/10.2307/2008346
  • [13] James H. Bramble, Joseph E. Pasciak, and Jinchao Xu, Parallel multilevel preconditioners, Math. Comp. 55 (1990), no. 191, 1-22. MR 1023042 (90k:65170), https://doi.org/10.2307/2008789
  • [14] James H. Bramble and Jinchao Xu, Some estimates for a weighted $ L^2$ projection, Math. Comp. 56 (1991), no. 194, 463-476. MR 1066830 (91k:65140), https://doi.org/10.2307/2008391
  • [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 $ H^1$ functions, SIAM J. Numer. Anal. 41 (2003), no. 1, 306-324. MR 1974504 (2004d:65140), 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 (2010f:65248), https://doi.org/10.1002/nla.630
  • [18] 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 (2008i:65286), 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 (2008c:65315)
  • [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 (2006c:65116), 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 (2006m:65256), 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 (2009c:65069), 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 (2010b:65065)
  • [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 (2009j:65309), 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 (electronic). MR 2257119 (2007m:65123), 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 (2009b:65077)
  • [28] Philippe G. Ciarlet, The finite element method for elliptic problems, North-Holland Publishing Co., Amsterdam, 1978. Studies in Mathematics and its Applications, Vol. 4. MR 0520174 (58 #25001)
  • [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 (2008k:65240), 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 (2007i:65088), 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 (2000i:65183), 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 (electronic). Dedicated to Raytcho Lazarov. MR 2002258 (2004i:65120)
  • [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 (2008m:65316), 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 (95m:65211), 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 (96d:65199), 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 (electronic). MR 1870847 (2003a:65113), 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 (2011h:65246), 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 (2004m:65179), 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 (2000h:65179), 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 (96a:65164), 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 (94k:65002)
  • [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 (electronic). MR 1921914 (2003g:65044), 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 (2007b:65005)
  • [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 (2009f:65251), 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 (2009b:65313), 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 (97a:65109), 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 (95k:65110)
  • [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] C. Pechstein and R. Scheichl.
    Weighted Poincaré inequalities and applications in domain decomposition, Lect. Notes Comput. Sci. Eng., 78, Springer, Heidelberg, 2011. MR 2867660
  • [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 (2010h:65209), https://doi.org/10.1137/080728457
  • [55] Marcus Sarkis, Multilevel methods for $ P_1$ nonconforming finite elements and discontinuous coefficients in three dimensions, (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 (98m:65199), 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 (90j:65021), https://doi.org/10.2307/2008497
  • [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 (2010b:65007)
  • [62] Jinchao Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev. 34 (1992), no. 4, 581-613. MR 1193013 (93k:65029), 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 (2008k:65271), 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 (2003f:65095), 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 (99m:65241), 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 (2009a:65084), 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 (2009g:65171), https://doi.org/10.1002/nla.556

Similar Articles

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
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

DOI: https://doi.org/10.1090/S0025-5718-2013-02760-3
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

American Mathematical Society