×

\(p\)-multigrid with partial smoothing: an efficient preconditioner for discontinuous Galerkin discretizations with modal bases. (English) Zbl 1519.65060

Authors’ abstract: Multigrid methods are efficient tools for the solution of linear systems arising in the discretization of partial differential equations and in other applications. While traditional multigrid methods often exhibit optimal or near-optimal computational cost, their application to advanced discretizations and complex geometries is challenging. In this work, we combine \(p\)-multigrid methods with algebraic multigrid (AMG) techniques to obtain scalable preconditioners for modal discontinuous Galerkin discretizations on complex, three-dimensional domains. We introduce the notion of partial smoothers, which update only a subset of the unknowns at each level of the multigrid hierarchy. Using partial smoothing, we incorporate hierarchical scale separation (HSS), a two-level \(p\)-multigrid-like technique with a more complete separation of high-order and low-order unknowns, into the existing p-multigrid framework. The resulting \(p\)-multigrid methods with partial smoothing are a generalization of existing HSS methods, offering tradeoffs between \(p\)-multigrid convergence and computational performance. In numerical experiments, we show that combined \(p\)-multigrid-AMG preconditioners can significantly accelerate large-scale simulations of pore scale flow, and we demonstrate that partial smoothing can further reduce computational cost by as much as 23%.
Reviewer: Wei Gong (Beijing)

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F08 Preconditioners for iterative methods
65Y05 Parallel numerical computation
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
76S05 Flows in porous media; filtration; seepage
74F10 Fluid-solid interactions (including aero- and hydro-elasticity, porosity, etc.)
74L10 Soil and rock mechanics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brandt, A.; Livne, O. E., Multigrid Techniques (2011), Society for Industrial and Applied Mathematics · Zbl 1227.65121
[2] Hackbusch, W., (Multi-Grid Methods and Applications. Multi-Grid Methods and Applications, Springer Series in Computational Mathematics, vol. 4 (1985), Springer-Verlag) · Zbl 0595.65106
[3] Brenner, S. C.; Zhao, J., Convergence of multigrid algorithms for interior penalty methods, Appl. Numer. Anal. Comput. Math., 2, 1, 3-18 (2005) · Zbl 1073.65117
[4] Vaněk, P.; Mandel, J.; Brezina, M., Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56, 3, 179-196 (1996) · Zbl 0851.65087
[5] Tamstorf, R.; Jones, T.; McCormick, S. F., Smoothed aggregation multigrid for cloth simulation, ACM Trans. Graph., 34, 6, 1-13 (2015)
[6] Stüben, K., A review of algebraic multigrid, J. Comput. Appl. Math., 128, 1-2, 281-309 (2001) · Zbl 0979.65111
[7] Briggs, W. L.; Henson, V. E.; McCormick, S. F., A Multigrid Tutorial (2000), Society for Industrial and Applied Mathematics · Zbl 0958.65128
[8] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Society for Industrial and Applied Mathematics · Zbl 1002.65042
[9] 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) · Zbl 1274.65313
[10] Li, J.; Riviere, B., High order discontinuous Galerkin method for simulating miscible flooding in porous media, Comput. Geosci., 19, 6, 1251-1268 (2015) · Zbl 1391.76732
[11] Fehn, N.; Munch, P.; Wall, W. A.; Kronbichler, M., Hybrid multigrid methods for high-order discontinuous Galerkin discretizations, J. Comput. Phys., 415, Article 109538 pp. (2020) · Zbl 1440.65135
[12] Bassi, F.; Rebay, S., Numerical solution of the Euler equations with a multiorder discontinuous finite element method, (Computational Fluid Dynamics 2002 (2003), Springer), 199-204 · Zbl 1140.76360
[13] Helenbrook, B.; Mavriplis, D.; Atkins, H., Analysis of p-multigrid for continuous and discontinuous finite element discretizations, (16th AIAA Computational Fluid Dynamics Conference (2003), American Institute of Aeronautics and Astronautics)
[14] Fidkowski, K. J.; Oliver, T. A.; Lu, J.; Darmofal, D. L., P-multigrid solution of high-order discontinuous Galerkin discretizations of the compressible Navier-Stokes equations, J. Comput. Phys., 207, 1, 92-113 (2005) · Zbl 1177.76194
[15] Luo, H.; Baum, J. D.; Löhner, R., Fast p-multigrid discontinuous Galerkin method for compressible flows at all speeds, AIAA J., 46, 3, 635-652 (2008)
[16] Bassi, F.; Ghidoni, A.; Rebay, S.; Tesini, P., High-order accurate p-multigrid discontinuous Galerkin solution of the Euler equations, Internat. J. Numer. Methods Fluids, 60, 8, 847-865 (2009) · Zbl 1165.76022
[17] Kuzmin, D., Hierarchical slope limiting in explicit and implicit discontinuous Galerkin methods, J. Comput. Phys., 257, 1140-1162 (2014) · Zbl 1352.65355
[18] Aizinger, V.; Kuzmin, D.; Korous, L., Scale separation in fast hierarchical solvers for discontinuous Galerkin methods, Appl. Math. Comput., 266, 838-849 (2015) · Zbl 1410.65362
[19] Thiele, C.; Araya-Polo, M.; Alpak, F. O.; Riviere, B.; Frank, F., Inexact hierarchical scale separation: A two-scale approach for linear systems from discontinuous Galerkin discretizations, Comput. Math. Appl., 74, 8, 1769-1778 (2017) · Zbl 1398.65088
[20] Schütz, J.; Aizinger, V., A hierarchical scale separation approach for the hybridized discontinuous Galerkin method, J. Comput. Appl. Math., 317, 500-509 (2017) · Zbl 1357.65267
[21] Jaust, A.; Schütz, J.; Aizinger, V., An efficient linear solver for the hybridized discontinuous Galerkin method, PAMM, 16, 1, 845-846 (2016)
[22] Rivière, B., Discontinuous Galerkin Methods for Solving Elliptic and Parabolic Equations: Theory and Implementation (2008), Society for Industrial and Applied Mathematics · Zbl 1153.65112
[23] Epshteyn, Y.; Rivière, B., Estimation of penalty parameters for symmetric interior penalty Galerkin methods, J. Comput. Appl. Math., 206, 2, 843-872 (2007) · Zbl 1141.65078
[24] Bank, R. E.; Dupont, T. F.; Yserentant, H., The hierarchical basis multigrid method, Numer. Math., 52, 4, 427-458 (1988) · Zbl 0645.65074
[25] Thiele, C., Composable p-hierarchical solver (2020), https://github.com/cthl/CPHIS, accessed: 13 March 2020
[26] Dagum, L.; Menon, R., OpenMP: An industry-standard API for shared-memory programming, Comput. Sci. Eng., 1, 46-55 (1998)
[27] Heroux, M. A.; Bartlett, R. A.; Howle, V. E.; Hoekstra, R. J.; Hu, J. J.; Kolda, T. G.; Lehoucq, R. B.; Long, K. R.; Pawlowski, R. P.; Phipps, E. T.; Salinger, A. G.; Thornquist, H. K.; Tuminaro, R. S.; Willenbring, J. M.; Williams, A.; Stanley, K. S., An overview of the Trilinos project, ACM Trans. Math. Software, 31, 3, 397-423 (2005) · Zbl 1136.65354
[28] Gropp, W.; Lusk, E.; Doss, N.; Skjellum, A., A high-performance, portable implementation of the MPI message passing interface standard, Parallel Comput., 22, 6, 789-828 (1996) · Zbl 0875.68206
[29] Balay, S.; Abhyankar, S.; Adams, M.; Brown, J.; Brune, P.; Buschelman, K.; Dalcin, L.; Dener, A.; Eijkhout, V.; Gropp, W., PETSc Users ManualTech. rep. (2019), Argonne National Laboratory
[30] Berger-Vergiat, L.; Glusa, C. A.; Hu, J. J.; Mayr, M.; Prokopenko, A.; Siefert, C. M.; Tuminaro, R. S.; Wiesner, T. A., MueLu User’s GuideTech. Rep. SAND2019-0537 (2019), Sandia National Laboratories
[31] Frank, F.; Liu, C.; Alpak, F. O.; Berg, S.; Riviere, B., Direct numerical simulation of flow on pore-scale images using the phase-field method, SPE J., 23, 05, 1833-1850 (2018)
[32] Frank, F.; Liu, C.; Alpak, F. O.; Riviere, B., A finite volume / discontinuous Galerkin method for the advective Cahn-Hilliard equation with degenerate mobility on porous domains stemming from micro-CT imaging, Comput. Geosci., 22, 2, 543-563 (2018) · Zbl 1405.65104
[33] Liu, C.; Frank, F.; Thiele, C.; Alpak, F. O.; Berg, S.; Chapman, W.; Riviere, B., An efficient numerical algorithm for solving viscosity contrast Cahn-Hilliard-Navier-Stokes system in porous media, J. Comput. Phys., 400, Article 108948 pp. (2019) · Zbl 1453.76078
[34] Trefethen, L. N.; Bau, D., Numerical Linear Algebra (1997), Society for Industrial and Applied Mathematics · Zbl 0874.65013
[35] Prokopenko, A.; Siefert, C. M.; Hu, J. J.; Hoemmen, M.; Klinvex, A., Ifpack2 User’s Guide 1.0Tech. Rep. SAND2016-5338 (2016)
[36] Hackbusch, W., (Iterative Solution of Large Sparse Systems of Equations. Iterative Solution of Large Sparse Systems of Equations, Applied Mathematical Sciences, vol. 95 (2016), Springer) · Zbl 1347.65063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.