An agglomeration-based massively parallel non-overlapping additive Schwarz preconditioner for high-order discontinuous Galerkin methods on polytopic grids

Antonietti, Paola; Houston, Paul; Pennesi, Giorgio; Süli, Endre

doi:10.1090/mcom/3510

An agglomeration-based massively parallel non-overlapping additive Schwarz preconditioner for high-order discontinuous Galerkin methods on polytopic grids
HTML articles powered by AMS MathViewer

by Paola F. Antonietti, Paul Houston, Giorgio Pennesi and Endre Süli;

Math. Comp. 89 (2020), 2047-2083

DOI: https://doi.org/10.1090/mcom/3510

Published electronically: February 18, 2020

HTML | PDF | Request permission

Abstract:

In this article we design and analyze a class of two-level non-overlapping additive Schwarz preconditioners for the solution of the linear system of equations stemming from discontinuous Galerkin discretizations of second-order elliptic partial differential equations on polytopic meshes. The preconditioner is based on a coarse space and a non-overlapping partition of the computational domain where local solvers are applied in parallel. In particular, the coarse space can potentially be chosen to be non-embedded with respect to the finer space; indeed it can be obtained from the fine grid by employing agglomeration and edge coarsening techniques. We investigate the dependence of the condition number of the preconditioned system with respect to the diffusion coefficient and the discretization parameters, i.e., the mesh size and the polynomial degree of the fine and coarse spaces. Numerical examples are presented which confirm the theoretical bounds.

References

P. F. Antonietti, L. Beirão da Veiga, D. Mora, and M. Verani, A stream virtual element formulation of the Stokes problem on polygonal meshes, SIAM J. Numer. Anal. 52 (2014), no. 1, 386–404. MR 3164557, DOI 10.1137/13091141X
Paola F. Antonietti, Franco Brezzi, and L. Donatella Marini, Bubble stabilization of discontinuous Galerkin methods, Comput. Methods Appl. Mech. Engrg. 198 (2009), no. 21-26, 1651–1659. MR 2517937, DOI 10.1016/j.cma.2008.12.033
Paola F. Antonietti, Andrea Cangiani, Joe Collis, Zhaonan Dong, Emmanuil H. Georgoulis, Stefano Giani, and Paul Houston, Review of discontinuous Galerkin finite element methods for partial differential equations on complicated domains, Building bridges: connections and challenges in modern approaches to numerical partial differential equations, Lect. Notes Comput. Sci. Eng., vol. 114, Springer, [Cham], 2016, pp. 279–308. MR 3585793
P. F. Antonietti, C. Facciolà, A. Russo, and M. Verani, Discontinuous Galerkin approximation of flows in fractured porous media, SIAM J. Sci. Comput. 41 (2019), no. 1, A109–A138.
Paola F. Antonietti, Luca Formaggia, Anna Scotti, Marco Verani, and Nicola Verzott, Mimetic finite difference approximation of flows in fractured porous media, ESAIM Math. Model. Numer. Anal. 50 (2016), no. 3, 809–832. MR 3507274, DOI 10.1051/m2an/2015087
Paola F. Antonietti, Stefano Giani, and Paul Houston, $hp$-version composite discontinuous Galerkin methods for elliptic problems on complicated domains, SIAM J. Sci. Comput. 35 (2013), no. 3, A1417–A1439. MR 3061474, DOI 10.1137/120877246
Paola F. Antonietti, Stefano Giani, and Paul Houston, Domain decomposition preconditioners for discontinuous Galerkin methods for elliptic problems on complicated domains, J. Sci. Comput. 60 (2014), no. 1, 203–227. MR 3246098, DOI 10.1007/s10915-013-9792-y
Paola F. Antonietti and Paul Houston, A class of domain decomposition preconditioners for $hp$-discontinuous Galerkin finite element methods, J. Sci. Comput. 46 (2011), no. 1, 124–149. MR 2753254, DOI 10.1007/s10915-010-9390-1
P. F. Antonietti, P. Houston, X. Hu, M. Sarti, and M. Verani, Multigrid algorithms for $hp$-version interior penalty discontinuous Galerkin methods on polygonal and polyhedral meshes, Calcolo 54 (2017), no. 4, 1169–1198. MR 3735810, DOI 10.1007/s10092-017-0223-6
Paola F. Antonietti, Paul Houston, and Iain Smears, A note on optimal spectral bounds for nonoverlapping domain decomposition preconditioners for $hp$-version discontinuous Galerkin methods, Int. J. Numer. Anal. Model. 13 (2016), no. 4, 513–524. MR 3506765
P. F. Antonietti, G. Manzini, and M. Verani, The fully nonconforming virtual element method for biharmonic problems, Math. Models Methods Appl. Sci. 28 (2018), no. 2, 387–407. MR 3741104, DOI 10.1142/S0218202518500100
P. F. Antonietti and I. Mazzieri, High-order discontinuous Galerkin methods for the elastodynamics equation on polygonal and polyhedral meshes, Comput. Methods Appl. Mech. Engrg. 342 (2018), 414–437. MR 3855145, DOI 10.1016/j.cma.2018.08.012
Paola F. Antonietti, Francesco Bonaldi, and Ilario Mazzieri, A high-order discontinuous Galerkin approach to the elasto-acoustic problem, Comput. Methods Appl. Mech. Engrg. 358 (2020), 112634, 29. MR 4011066, DOI 10.1016/j.cma.2019.112634
P. F. Antonietti and G. Pennesi, $V$-cycle multigrid algorithms for discontinuous Galerkin methods on non-nested polytopic meshes, J. Sci. Comput. 78 (2019), no. 1, 625–652. MR 3902899, DOI 10.1007/s10915-018-0783-x
Paola F. Antonietti, Marco Sarti, and Marco Verani, Multigrid algorithms for $hp$-discontinuous Galerkin discretizations of elliptic problems, SIAM J. Numer. Anal. 53 (2015), no. 1, 598–618. MR 3315225, DOI 10.1137/130947015
Paola Antonietti, Marco Verani, Christian Vergara, and Stefano Zonca, Numerical solution of fluid-structure interaction problems by means of a high order Discontinuous Galerkin method on polygonal grids, Finite Elem. Anal. Des. 159 (2019), 1–14. MR 3924531, DOI 10.1016/j.finel.2019.02.002
Douglas N. Arnold, An interior penalty finite element method with discontinuous elements, SIAM J. Numer. Anal. 19 (1982), no. 4, 742–760. MR 664882, DOI 10.1137/0719052
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
Blanca Ayuso de Dios, Konstantin Lipnikov, and Gianmarco Manzini, The nonconforming virtual element method, ESAIM Math. Model. Numer. Anal. 50 (2016), no. 3, 879–904. MR 3507277, DOI 10.1051/m2an/2015090
Francesco Bassi, Lorenzo Botti, and Alessandro Colombo, Agglomeration-based physical frame dG discretizations: an attempt to be mesh free, Math. Models Methods Appl. Sci. 24 (2014), no. 8, 1495–1539. MR 3200241, DOI 10.1142/S0218202514400028
F. Bassi, L. Botti, A. Colombo, D. A. Di Pietro, and P. Tesini, On the flexibility of agglomeration based physical space discontinuous Galerkin discretizations, J. Comput. Phys. 231 (2012), no. 1, 45–65. MR 2846986, DOI 10.1016/j.jcp.2011.08.018
L. Beirão da Veiga, F. Brezzi, A. Cangiani, G. Manzini, L. D. Marini, and A. Russo, Basic principles of virtual element methods, Math. Models Methods Appl. Sci. 23 (2013), no. 1, 199–214. MR 2997471, DOI 10.1142/S0218202512500492
L. Beirão da Veiga, F. Brezzi, L. D. Marini, and A. Russo, Virtual element method for general second-order elliptic problems on polygonal meshes, Math. Models Methods Appl. Sci. 26 (2016), no. 4, 729–750. MR 3460621, DOI 10.1142/S0218202516500160
Lourenço Beirão da Veiga, Konstantin Lipnikov, and Gianmarco Manzini, The mimetic finite difference method for elliptic problems, MS&A. Modeling, Simulation and Applications, vol. 11, Springer, Cham, 2014. MR 3135418, DOI 10.1007/978-3-319-02663-3
S. C. Brenner, J. Cui, T. Gudi, and L.-Y. Sung, Multigrid algorithms for symmetric discontinuous Galerkin methods on graded meshes, Numer. Math. 119 (2011), no. 1, 21–47. MR 2824854, DOI 10.1007/s00211-011-0379-y
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
Franco Brezzi, Konstantin Lipnikov, and Mikhail Shashkov, Convergence of the mimetic finite difference method for diffusion problems on polyhedral meshes, SIAM J. Numer. Anal. 43 (2005), no. 5, 1872–1896. MR 2192322, DOI 10.1137/040613950
Franco Brezzi, Konstantin Lipnikov, and Valeria Simoncini, A family of mimetic finite difference methods on polygonal and polyhedral meshes, Math. Models Methods Appl. Sci. 15 (2005), no. 10, 1533–1551. MR 2168945, DOI 10.1142/S0218202505000832
Andrea Cangiani, Zhaonan Dong, and Emmanuil H. Georgoulis, $hp$-version space-time discontinuous Galerkin methods for parabolic problems on prismatic meshes, SIAM J. Sci. Comput. 39 (2017), no. 4, A1251–A1279. MR 3672375, DOI 10.1137/16M1073285
Andrea Cangiani, Zhaonan Dong, Emmanuil H. Georgoulis, and Paul Houston, $hp$-version discontinuous Galerkin methods on polygonal and polyhedral meshes, SpringerBriefs in Mathematics, Springer, Cham, 2017. MR 3729265
Andrea Cangiani, Emmanuil H. Georgoulis, and Paul Houston, $hp$-version discontinuous Galerkin methods on polygonal and polyhedral meshes, Math. Models Methods Appl. Sci. 24 (2014), no. 10, 2009–2041. MR 3211116, DOI 10.1142/S0218202514500146
Andrea Cangiani, Gianmarco Manzini, and Oliver J. Sutton, Conforming and nonconforming virtual element methods for elliptic problems, IMA J. Numer. Anal. 37 (2017), no. 3, 1317–1354. MR 3671497, DOI 10.1093/imanum/drw036
Bernardo Cockburn, Bo Dong, and Johnny Guzmán, A superconvergent LDG-hybridizable Galerkin method for second-order elliptic problems, Math. Comp. 77 (2008), no. 264, 1887–1916. MR 2429868, DOI 10.1090/S0025-5718-08-02123-6
Bernardo Cockburn, Jayadeep Gopalakrishnan, and Raytcho Lazarov, Unified hybridization of discontinuous Galerkin, mixed, and continuous Galerkin methods for second order elliptic problems, SIAM J. Numer. Anal. 47 (2009), no. 2, 1319–1365. MR 2485455, DOI 10.1137/070706616
Daniele A. Di Pietro and Alexandre Ern, A hybrid high-order locking-free method for linear elasticity on general meshes, Comput. Methods Appl. Mech. Engrg. 283 (2015), 1–21. MR 3283758, DOI 10.1016/j.cma.2014.09.009
D. A. Di Pietro and A. Ern, Hybrid High-Order methods for variable-diffusion problems on general meshes, C. R. Math. Acad. Sci. Soc. R. Can. 353 (2015January), no. 1, 31–34.
Daniele A. Di Pietro, Alexandre Ern, and Simon Lemaire, An arbitrary-order and compact-stencil discretization of diffusion on general meshes based on local reconstruction operators, Comput. Methods Appl. Math. 14 (2014), no. 4, 461–472. MR 3259024, DOI 10.1515/cmam-2014-0018
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
Jérome Droniou, Robert Eymard, and Raphaèle Herbin, Gradient schemes: generic tools for the numerical analysis of diffusion equations, ESAIM Math. Model. Numer. Anal. 50 (2016), no. 3, 749–781. MR 3507272, DOI 10.1051/m2an/2015079
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 and Piotr Krzyżanowski, A massively parallel nonoverlapping additive Schwarz method for discontinuous Galerkin discretization of elliptic problems, Numer. Math. 132 (2016), no. 2, 347–367. MR 3447135, DOI 10.1007/s00211-015-0718-5
M. Dryja and M. Sarkis, Additive average Schwarz methods for discretization of elliptic problems with highly discontinuous coefficients, Comput. Methods Appl. Math. 10 (2010), no. 2, 164–176. MR 2770288, DOI 10.2478/cmam-2010-0009
Alexandre Ern, Annette F. Stephansen, and Paolo Zunino, A discontinuous Galerkin method with weighted averages for advection-diffusion equations with locally small and anisotropic diffusivity, IMA J. Numer. Anal. 29 (2009), no. 2, 235–256. MR 2491426, DOI 10.1093/imanum/drm050
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
Thomas-Peter Fries and Ted Belytschko, The extended/generalized finite element method: an overview of the method and its applications, Internat. J. Numer. Methods Engrg. 84 (2010), no. 3, 253–304. MR 2732652, DOI 10.1002/nme.2914
E. H. Georgoulis and O. Lakkis, A posteriori error bounds for discontinuous Galerkin methods for quasilinear parabolic problems, Numerical mathematics and advanced applications 2009, 2010, pp. 351–358.
J. Gopalakrishnan and G. Kanschat, A multilevel discontinuous Galerkin method, Numer. Math. 95 (2003), no. 3, 527–550. MR 2012931, DOI 10.1007/s002110200392
P. Grisvard, Elliptic problems in nonsmooth domains, Monographs and Studies in Mathematics, vol. 24, Pitman (Advanced Publishing Program), Boston, MA, 1985. MR 775683
W. Hackbusch and S. A. Sauter, Composite Finite Elements for problems containing small geometric details. Part II: Implementation and numerical results, Comput. Visual Sci. 1 (1997), no. 4, 15–25.
James Hyman, Mikhail Shashkov, and Stanly Steinberg, The numerical solution of diffusion problems in strongly heterogeneous non-isotropic materials, J. Comput. Phys. 132 (1997), no. 1, 130–148. MR 1440338, DOI 10.1006/jcph.1996.5633
Ohannes Karakashian and Craig Collins, Two-level additive Schwarz methods for discontinuous Galerkin approximations of second-order elliptic problems, IMA J. Numer. Anal. 37 (2017), no. 4, 1800–1830. MR 3712175, DOI 10.1093/imanum/drw061
G. Karypis and V. Kumar, Metis: Unstructured graph partitioning and sparse matrix ordering system, version 4.0, 2009.
P. Krzyżanowski, On a nonoverlapping additive schwarz method for h-p discontinuous galerkin discretization of elliptic problems, Num. Meth. Part. Diff. Eqs. 32 (2016), no. 6, 1572–1590.
P.-L. Lions, On the Schwarz alternating method. I, First International Symposium on Domain Decomposition Methods for Partial Differential Equations (Paris, 1987) SIAM, Philadelphia, PA, 1988, pp. 1–42. MR 972510
L. E. Payne and H. F. Weinberger, An optimal Poincaré inequality for convex domains, Arch. Rational Mech. Anal. 5 (1960), 286–292 (1960). MR 117419, DOI 10.1007/BF00252910
S.A. Sauter, A remark on extension theorems for domains having small geometric details, Technical report 96-03, University of Kiel (1996).
S. A. Sauter and R. Warnke, Extension operators and approximation on domains containing small geometric details, East-West J. Numer. Math. 7 (1999), no. 1, 61–77. MR 1683936
Iain Smears, Nonoverlapping domain decomposition preconditioners for discontinuous Galerkin approximations of Hamilton-Jacobi-Bellman equations, J. Sci. Comput. 74 (2018), no. 1, 145–174. MR 3742874, DOI 10.1007/s10915-017-0428-5
Elias M. Stein, Singular integrals and differentiability properties of functions, Princeton Mathematical Series, No. 30, Princeton University Press, Princeton, NJ, 1970. MR 290095
N. Sukumar and A. Tabarraei, Conforming polygonal finite elements, Internat. J. Numer. Methods Engrg. 61 (2004), no. 12, 2045–2066. MR 2101599, DOI 10.1002/nme.1141
A. Tabarraei and N. Sukumar, Extended finite element method on polygonal and quadtree meshes, Comput. Methods Appl. Mech. Engrg. 197 (2007), no. 5, 425–438. MR 2362382, DOI 10.1016/j.cma.2007.08.013
Andrea Toselli and Olof Widlund, Domain decomposition methods—algorithms and theory, Springer Series in Computational Mathematics, vol. 34, Springer-Verlag, Berlin, 2005. MR 2104179, DOI 10.1007/b137868
Mary Fanett Wheeler, An elliptic collocation-finite element method with interior penalties, SIAM J. Numer. Anal. 15 (1978), no. 1, 152–161. MR 471383, DOI 10.1137/0715010
Weiying Zheng and He Qi, On Friedrichs-Poincaré-type inequalities, J. Math. Anal. Appl. 304 (2005), no. 2, 542–551. MR 2126549, DOI 10.1016/j.jmaa.2004.09.066