Uniform Subspace Correction Preconditioners for Discontinuous Galerkin Methods with hp-Refnement

doi:10.1007/s42967-021-00136-3

Communications on Applied Mathematics and Computation ›› 2022, Vol. 4 ›› Issue (2): 697-727.doi: 10.1007/s42967-021-00136-3

• ORIGINAL PAPERS • 上一篇下一篇

Uniform Subspace Correction Preconditioners for Discontinuous Galerkin Methods with hp-Refnement

Will Pazner, Tzanio Kolev

Lawrence Livermore National Laboratory, Center for Applied Scientifc Computing, Livermore, CA, USA

收稿日期:2020-08-31 修回日期:2021-02-06 出版日期:2022-06-20 发布日期:2022-04-29
通讯作者: Will Pazner E-mail:pazner1@llnl.gov
基金资助:
This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under Contract DE-AC52-07NA27344 and was partially supported by the LLNL-LDRD Program under Project No. 20-ERD-002 (LLNL-JRNL-814157). This document was prepared as an account of work sponsored by an agency of the United States government. Neither the United States government nor Lawrence Livermore National Security, LLC, nor any of their employees makes any warranty, expressed or implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any information, apparatus, product, or process disclosed, or represents that its use would not infringe privately owned rights. Reference herein to any specifc commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not necessarily constitute or imply its endorsement, recommendation, or favoring by the United States government or Lawrence Livermore National Security, LLC. The views and opinions of authors expressed herein do not necessarily state or refect those of the United States government or Lawrence Livermore National Security, LLC, and shall not be used for advertising or product endorsement purposes.

Uniform Subspace Correction Preconditioners for Discontinuous Galerkin Methods with hp-Refnement

Will Pazner, Tzanio Kolev

Lawrence Livermore National Laboratory, Center for Applied Scientifc Computing, Livermore, CA, USA

Received:2020-08-31 Revised:2021-02-06 Online:2022-06-20 Published:2022-04-29
Contact: Will Pazner E-mail:pazner1@llnl.gov
Supported by:
This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under Contract DE-AC52-07NA27344 and was partially supported by the LLNL-LDRD Program under Project No. 20-ERD-002 (LLNL-JRNL-814157). This document was prepared as an account of work sponsored by an agency of the United States government. Neither the United States government nor Lawrence Livermore National Security, LLC, nor any of their employees makes any warranty, expressed or implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any information, apparatus, product, or process disclosed, or represents that its use would not infringe privately owned rights. Reference herein to any specifc commercial product, process, or service by trade name, trademark, manufacturer, or otherwise does not necessarily constitute or imply its endorsement, recommendation, or favoring by the United States government or Lawrence Livermore National Security, LLC. The views and opinions of authors expressed herein do not necessarily state or refect those of the United States government or Lawrence Livermore National Security, LLC, and shall not be used for advertising or product endorsement purposes.

摘要/Abstract

摘要： In this paper, we develop subspace correction preconditioners for discontinuous Galerkin (DG) discretizations of elliptic problems with hp-refnement. These preconditioners are based on the decomposition of the DG fnite element space into a conforming subspace, and a set of small nonconforming edge spaces. The conforming subspace is preconditioned using a matrix-free low-order refned technique, which in this work, we extend to the hp-refnement context using a variational restriction approach. The condition number of the resulting linear system is independent of the granularity of the mesh h, and the degree of the polynomial approximation p. The method is amenable to use with meshes of any degree of irregularity and arbitrary distribution of polynomial degrees. Numerical examples are shown on several test cases involving adaptively and randomly refned meshes, using both the symmetric interior penalty method and the second method of Bassi and Rebay (BR2).

关键词: Discontinuous Galerkin, Preconditioners, Domain decomposition, hp-refnement

Abstract: In this paper, we develop subspace correction preconditioners for discontinuous Galerkin (DG) discretizations of elliptic problems with hp-refnement. These preconditioners are based on the decomposition of the DG fnite element space into a conforming subspace, and a set of small nonconforming edge spaces. The conforming subspace is preconditioned using a matrix-free low-order refned technique, which in this work, we extend to the hp-refnement context using a variational restriction approach. The condition number of the resulting linear system is independent of the granularity of the mesh h, and the degree of the polynomial approximation p. The method is amenable to use with meshes of any degree of irregularity and arbitrary distribution of polynomial degrees. Numerical examples are shown on several test cases involving adaptively and randomly refned meshes, using both the symmetric interior penalty method and the second method of Bassi and Rebay (BR2).

Key words: Discontinuous Galerkin, Preconditioners, Domain decomposition, hp-refnement

中图分类号:

Will Pazner, Tzanio Kolev. Uniform Subspace Correction Preconditioners for Discontinuous Galerkin Methods with hp-Refnement[J]. Communications on Applied Mathematics and Computation, 2022, 4(2): 697-727.

参考文献

1.Anderson, R., et al.:MFEM:a modular fnite element methods library.Comput.Math.Appl.81, 42-74 (2021).https://doi.org/10.1016/j.camwa.2020.06.009
2.Antonietti, P.F., Ayuso, B.:Schwarz domain decomposition preconditioners for discontinuous Galerkin approximations of elliptic problems:non-overlapping case.ESAIM:Mathematical Modelling and Numerical Analysis 41(1), 21-54 (2007) https://doi.org/10.1051/m2an:2007006
3.Antonietti, P.F., Giani, S., Houston, P.:Domain decomposition preconditioners for discontinuous Galerkin methods for elliptic problems on complicated domains.J.Sci.Comput.60(1), 203-227 (2013) https://doi.org/10.1007/s10915-013-9792-y
4.Antonietti, P.F., Houston, P.:A class of domain decomposition preconditioners for hp-discontinuous Galerkin fnite element methods.J.Sci.Comput.46(1), 124-149 (2010) https://doi.org/10.1007/s10915-010-9390-1
5.Antonietti, P.F., Houston, P., Pennesi, G., Suli, E.:An agglomeration-based massively parallel nonoverlapping additive Schwarz preconditioner for high-order discontinuous Galerkin methods on polytopic grids.Math.Comput.89(325), 2047-2083 (2020) https://doi.org/10.1090/mcom/3510
6.Antonietti, P.F., Houston, P., Smears, I.:A note on optimal spectral bounds for nonoverlapping domain decomposition preconditioners for hp-version discontinuous Galerkin methods.Int.J.Numer.Anal.Model.13(4), 513-524 (2016)
7.Antonietti, P.F., Melas, L.:Algebraic multigrid schemes for high-order nodal discontinuous Galerkin methods.SIAM J.Sci.Comput.42(2), A1147-A1173 (2020) https://doi.org/10.1137/18m12 04383
8.Antonietti, P.F., Sarti, M., Verani, M.:Multigrid algorithms for hp-discontinuous Galerkin discretizations of elliptic problems.SIAM J.Numer.Anal.53(1), 598-618 (2015) https://doi.org/10.1137/130947015
9.Antonietti, P.F., Sarti, M., Verani, M., Zikatanov, L.T.:A uniform additive Schwarz preconditioner for high-order discontinuous Galerkin approximations of elliptic problems.J.Sci.Comput.70(2), 608-630 (2016) https://doi.org/10.1007/s10915-016-0259-9
10.Arnold, D.N.:An interior penalty fnite element method with discontinuous elements.SIAM J.Numer.Anal.19(4), 742-760 (1982) https://doi.org/10.1137/0719052
11.Arnold, D.N., Brezzi, F., Cockburn, B., Marini, L.D.:Unifed analysis of discontinuous Galerkin methods for elliptic problems.SIAM J.Numer.Anal.39(5), 1749-1779 (2002) https://doi.org/10.1137/S0036142901384162
12.Bassi, F., Rebay, S.:A high order discontinuous Galerkin method for compressible turbulent fows.In:Cockburn, B., Karniadakis, G.E., Shu, C.-W.(eds.) Discontinuous Galerkin Methods, vol.11, pp.77-88.Springer, Berlin (2000) https://doi.org/10.1007/978-3-642-59721-3_4
13.Bastian, P., Blatt, M., Scheichl, R.:Algebraic multigrid for discontinuous Galerkin discretizations of heterogeneous elliptic problems.Numer.Linear Algebra Appl.19(2), 367-388 (2012) https://doi.org/10.1002/nla.1816
14.Bernardi, C., Maday, Y., Rapetti, F.:Basics and some applications of the mortar element method.GAMM-Mitteilungen 28(2), 97-123 (2005) https://doi.org/10.1002/gamm.201490020
15.Braess, D.:Finite Elements:Theory, Fast Solvers, and Applications in Solid Mechanics.Cambridge University Press, Cambridge (2007) https://doi.org/10.1017/cbo9780511618635
16.Brix, K., Campos Pinto, M., Canuto, C., Dahmen, W.:Multilevel preconditioning of discontinuous Galerkin spectral element methods.Part I:geometrically conforming meshes.IMA J.Numer.Anal.35(4), 1487-1532 (2014).https://doi.org/10.1093/imanum/dru053
17.Brix, K., Pinto, M.C., Dahmen, W.:A multilevel preconditioner for the interior penalty discontinuous Galerkin method.SIAM J.Numer.Anal.46(5), 2742-2768 (2008) https://doi.org/10.1137/07069691x
18.Burman, E., Ern, A.:Continuous interior penalty hp-fnite element methods for advection and advection-difusion equations.Math.Comput.76(259), 1119-1141 (2007) https://doi.org/10.1090/s0025-5718-07-01951-5
19.Canuto, C.:Stabilization of spectral methods by fnite element bubble functions.Comput.Methods Appl.Mech.Eng.116(1/2/3/4), 13-26 (1994)
20.Canuto, C., Gervasio, P., Quarteroni, A.:Finite-element preconditioning of G-NI spectral methods.SIAM J.Sci.Comput.31(6), 4422-4451 (2010) https://doi.org/10.1137/090746367
21.Canuto, C., Hussaini, M.Y., Quarteroni, A., Zang, T.A.:Spectral Methods:Fundamentals in Single Domains.Springer, Berlin (2006) https://doi.org/10.1007/978-3-540-30726-6
22.Canuto, C., Quarteroni, A.:Approximation results for orthogonal polynomials in Sobolev spaces.Math.Comput.38(157), 67-86 (1982) https://doi.org/10.1090/s0025-5718-1982-0637287-3
23.Castillo, P.:Performance of discontinuous Galerkin methods for elliptic PDEs.SIAM J.Sci.Comput.24(2), 524-547 (2002) https://doi.org/10.1137/s1064827501388339
24.Červený, J., Dobrev, V., Kolev, T.:Nonconforming mesh refnement for high-order fnite elements.SIAM J.Sci.Comput.41(4), C367-C392 (2019) https://doi.org/10.1137/18m1193992
25.Chung, E.T., Kim, H.H., Widlund, O.B.:Two-level overlapping Schwarz algorithms for a staggered discontinuous Galerkin method.SIAM J.Numer.Anal.51(1), 47-67 (2013) https://doi.org/10.1137/110849432
26.Cockburn, B., Shu, C.-W.:The local discontinuous Galerkin method for time-dependent convection difusion systems.SIAM J.Numer.Anal.35(6), 2440-2463 (1998) https://doi.org/10.1137/s0036 142997316712
27.Cockburn, B., Shu, C.-W.:Runge-Kutta discontinuous Galerkin methods for convection-dominated problems.J.Sci.Comput.16(3), 173-261 (2001) https://doi.org/10.1023/a:1012873910884
28.Demkowicz, L., Rachowicz, W., Devloo, P.:A fully automatic hp-adaptivity.J.Sci.Comput.17(1/2/3/4), 117-142 (2002) https://doi.org/10.1023/a:1015192312705
29.Dobrev, V.A., Lazarov, R.D., Vassilevski, P.S., Zikatanov, L.T.:Two-level preconditioning of discontinuous Galerkin approximations of second-order elliptic equations.Numer.Linear Algebra Appl.13(9), 753-770 (2006) https://doi.org/10.1002/nla.504
30.Dryja, M., Widlund, O.B.:Some domain decomposition algorithms for elliptic problems.In:Kincaid, D.R., Hayes, L.J.(eds.) Iterative Methods for Large Linear Systems, pp.273-291.Academic Press, New York (1990).https://doi.org/10.1016/B978-0-12-407475-0.50022-X
31.Fehn, N., Wall, W.A., Kronbichler, M.:On the stability of projection methods for the incompressible Navier-Stokes equations based on high-order discontinuous Galerkin discretizations.J.Comput.Phys.351, 392-421 (2017) https://doi.org/10.1016/j.jcp.2017.09.031
32.Fortunato, D., Rycroft, C.H., Saye, R.:Efcient operator-coarsening multigrid schemes for local discontinuous Galerkin methods.SIAM J.Sci.Comput.41(6), A3913-A3937 (2019) https://doi.org/10.1137/18m1206357
33.Gopalakrishnan, J., Kanschat, G.:A multilevel discontinuous Galerkin method.Numer.Math.95(3), 527-550 (2003) https://doi.org/10.1007/s002110200392
34.Griebel, M., Oswald, P.:On the abstract theory of additive and multiplicative Schwarz algorithms.Numer.Math.70(2), 163-180 (1995) https://doi.org/10.1007/s002110050115
35.Haut, T.S., Southworth, B.S., Maginot, P.G., Tomov, V.Z.:Difusion synthetic acceleration preconditioning for discontinuous Galerkin discretizations of SN transport on high-order curved meshes.SIAM J.Sci.Comput.42(5), B1271-B1301 (2020) https://doi.org/10.1137/19m124993x
36.Henson, V.E., Yang, U.M.:BoomerAMG:a parallel algebraic multigrid solver and preconditioner.Appl.Numer.Math.41(1), 155-177 (2002) https://doi.org/10.1016/s0168-9274(01)00115-5
37.Houston, P., Schötzau, D., Wihler, T.P.:Energy norm a posteriori error estimation of hp-adaptive discontinuous Galerkin methods for elliptic problems.Math.Models Methods Appl.Sci.17(01), 33-62 (2007) https://doi.org/10.1142/s0218202507001826
38.Houston, P., Süli, E., Wihler, T.P.:A posteriori error analysis of hp-version discontinuous Galerkin fnite-element methods for second-order quasi-linear elliptic PDEs.IMA J.Numer.Anal.28(2), 245-273 (2007) https://doi.org/10.1093/imanum/drm009
39.Kanschat, G.:Multilevel methods for discontinuous Galerkin FEM on locally refned meshes.Comput.Struct.82(28), 2437-2445 (2004) https://doi.org/10.1016/j.compstruc.2004.04.015
40.Karakashian, O.A., Pascal, F.:A posteriori error estimates for a discontinuous Galerkin approximation of second-order elliptic problems.SIAM J.Numer.Anal.41(6), 2374-2399 (2003) https://doi.org/10.1137/s0036142902405217
41.Melenk, J., Gerdes, K., Schwab, C.:Fully discrete hp-fnite elements:fast quadrature.Comput.Methods Appl.Mech.Eng.190(32/33), 4339-4364 (2001) https://doi.org/10.1016/s0045-7825(00)00322-4
42.MFEM:Modular Finite Element Methods[Software].www.mfem.org https://doi.org/10.11578/dc.20171025.1248
43.Orszag, S.A.:Spectral methods for problems in complex geometries.J.Comput.Phys.37(1), 70-92 (1980) https://doi.org/10.1016/0021-9991(80)90005-4
44.Oswald, P.:On a BPX-preconditioner for P1 elements.Computing 51(2), 125-133 (1993) https://doi.org/10.1007/bf02243847
45.Pazner, W.:Efcient low-order refned preconditioners for high-order matrix-free continuous and discontinuous Galerkin methods.J.Sci.Comput.42(5), A3055-A3083 (2020)
46.Peraire, J., Persson, P.-O.:The compact discontinuous Galerkin (CDG) method for elliptic problems.SIAM J.Sci.Comput.30(4), 1806-1824 (2008) https://doi.org/10.1137/070685518
47.Pazner, W., Persson, P.-O.:Approximate tensor-product preconditioners for very high order discontinuous Galerkin methods.J.Comput.Phys.354, 344-369 (2018) https://doi.org/10.1016/j.jcp.2017.10.030
48.Perugia, I., Schötzau, D.:An hp-analysis of the local discontinuous Galerkin method for difusion problems.J.Sci.Comput.17(1/2/3/4), 561-571 (2002) https://doi.org/10.1023/a:1015118613130
49.Shahbazi, K.:An explicit expression for the penalty parameter of the interior penalty method.J.Comput.Phys.205(2), 401-407 (2005) https://doi.org/10.1016/j.jcp.2004.11.017
50.Shahbazi, K., Fischer, P.F., Ethier, C.R.:A high-order discontinuous Galerkin method for the unsteady incompressible Navier-Stokes equations.J.Comput.Phys.222(1), 391-407 (2007).https://doi.org/10.1016/j.jcp.2006.07.029
51.Šolín, P., Červený, J., Doležel, I.:Arbitrary-level hanging nodes and automatic adaptivity in the hpFEM.Math.Comput.Simul.77(1), 117-132 (2008) https://doi.org/10.1016/j.matcom.2007.02.011
52.Szabó, B., Babuška, I.:Wiley Series in Computational Mechanics.Finite Element Analysis.Wiley, Amsterdam (1991)
53.Toselli, A., Widlund, O.B.:Domain Decomposition Methods-Algorithms and Theory.Springer Series in Computational Mathematics.Springer-Verlag, Berlin/Heidelberg (2005).https://doi.org/10.1007/b137868
54.Wang, Z., et al.:High-order CFD methods:current status and perspective.Int.J.Numer.Meth.Fluids 72(8), 811-845 (2013) https://doi.org/10.1002/fd.3767
55.Wihler, T., Frauenfelder, P., Schwab, C.:Exponential convergence of the hp-DGFEM for difusion problems.Comput.Math.Appl.46(1), 183-205 (2003) https://doi.org/10.1016/s0898-1221(03) 90088-5
56.Xu, J.:Iterative methods by space decomposition and subspace correction.SIAM Rev.34(4), 581-613 (1992) https://doi.org/10.1137/1034116
57.Xu, J.:The method of subspace corrections.J.Comput.Appl.Math.128(1/2), 335-362 (2001) https://doi.org/10.1016/s0377-0427(00)00518-5
58.Xu, J., Zikatanov, L.:The method of alternating projections and the method of subspace corrections in Hilbert space.J.Am.Math.Soc.15(03), 573-598 (2002) https://doi.org/10.1090/s0894-0347-02-00398-3
59.Zhu, L., Giani, S., Houston, P., Schötzau, D.:Energy norm a posteriori error estimation for hp-adaptive discontinuous Galerkin methods for elliptic problems in three dimensions.Math.Models Methods Appl.Sci.21(02), 267-306 (2011) https://doi.org/10.1142/s0218202511005052
60.Zhu, L., Schötzau, D.:A robust a posteriori error estimate for hp-adaptive DG methods for convectiondifusion equations.IMA J.Numer.Anal.31(3), 971-1005 (2010) https://doi.org/10.1093/imanum/drp038

[1]	Xiu Ye, Shangyou Zhang. Two-Order Superconvergent CDG Finite Element Method for the Heat Equation on Triangular and Tetrahedral Meshes[J]. Communications on Applied Mathematics and Computation, 2026, 8(2): 411-426.
[2]	Wei Zheng, Yan Xu. Invariants Preserving Time-Implicit Local Discontinuous Galerkin Schemes for High-Order Nonlinear Wave Equations[J]. Communications on Applied Mathematics and Computation, 2026, 8(1): 149-176.
[3]	Qiaoqiao Dai, Dongxia Li. The L2-1_σ/LDG Method for the Caputo Diffusion Equation with a Variable Coefficient[J]. Communications on Applied Mathematics and Computation, 2025, 7(4): 1378-1397.
[4]	Xiu Ye, Shangyou Zhang. Constructing a CDG Finite Element with Order Two Superconvergence on Rectangular Meshes[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 411-425.
[5]	Qigang Liang, Wei Wang, Xuejun Xu. A Domain Decomposition Method for Nonconforming Finite Element Approximations of Eigenvalue Problems[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 606-636.
[6]	Yuan Xu, Qiang Zhang. A Note on Stability Analysis of Two-Dimensional Runge-Kutta Discontinuous Galerkin Methods[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 637-662.
[7]	Mengfei Wang, Yan Xu. Superconvergence of UWLDG Method for One-Dimensional Linear Sixth-Order Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 771-795.
[8]	Lei Yang, Shun Li, Yan Jiang, Chi-Wang Shu, Mengping Zhang. Inverse Lax-Wendroff Boundary Treatment of Discontinuous Galerkin Method for 1D Conservation Laws[J]. Communications on Applied Mathematics and Computation, 2025, 7(2): 796-826.
[9]	Meiqi Tan, Juan Cheng, Chi-Wang Shu. The High-Order Variable-Coefficient Explicit-Implicit-Null Method for Diffusion and Dispersion Equations[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 115-150.
[10]	Zhen Wang. L1/LDG Method for Caputo-Hadamard Time Fractional Diffusion Equation[J]. Communications on Applied Mathematics and Computation, 2025, 7(1): 203-227.
[11]	Laura Río-Martín, Michael Dumbser. High-Order ADER Discontinuous Galerkin Schemes for a Symmetric Hyperbolic Model of Compressible Barotropic Two-Fluid Flows[J]. Communications on Applied Mathematics and Computation, 2024, 6(4): 2119-2154.
[12]	Lin Mu, Xiu Ye, Shangyou Zhang, Peng Zhu. A DG Method for the Stokes Equations on Tensor Product Meshes with [P_k]^d-P_k-1 Element[J]. Communications on Applied Mathematics and Computation, 2024, 6(4): 2431-2454.
[13]	Andrés M. Rueda-Ramírez, Benjamin Bolm, Dmitri Kuzmin, Gregor J. Gassner. Monolithic Convex Limiting for Legendre-Gauss-Lobatto Discontinuous Galerkin Spectral-Element Methods[J]. Communications on Applied Mathematics and Computation, 2024, 6(3): 1860-1898.
[14]	Michel Bergmann, Afaf Bouharguane, Angelo Iollo, Alexis Tardieu. High Order ADER-IPDG Methods for the Unsteady Advection-Diffusion Equation[J]. Communications on Applied Mathematics and Computation, 2024, 6(3): 1954-1977.
[15]	Janina Bender, Philipp Öffner. Entropy-Conservative Discontinuous Galerkin Methods for the Shallow Water Equations with Uncertainty[J]. Communications on Applied Mathematics and Computation, 2024, 6(3): 1978-2010.

Uniform Subspace Correction Preconditioners for Discontinuous Galerkin Methods with hp-Refnement

Uniform Subspace Correction Preconditioners for Discontinuous Galerkin Methods with hp-Refnement

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价