Adaptive Sparse Grid Discontinuous Galerkin Method: Review and Software Implementation

doi:10.1007/s42967-023-00268-8

Communications on Applied Mathematics and Computation ›› 2024, Vol. 6 ›› Issue (1): 501-532.doi: 10.1007/s42967-023-00268-8

• ORIGINAL PAPERS • 上一篇下一篇

Adaptive Sparse Grid Discontinuous Galerkin Method: Review and Software Implementation

Juntao Huang^1,2, Wei Guo¹, Yingda Cheng³

1. Department of Mathematics and Statistics, Texas Tech University, Lubbock, TX, 79409, USA;
2. Department of Computational Mathematics, Science and Engineering, Michigan State University, East Lansing, MI, 48824, USA;
3. Department of Mathematics, Michigan State University, East Lansing, MI, 48824, USA

收稿日期:2022-11-02 修回日期:2023-02-06 发布日期:2024-04-16
通讯作者: Yingda Cheng,E-mail:ycheng@msu.edu;Juntao Huang,E-mail:juntao.huang@ttu.edu;Wei Guo,E-mail:weimath.guo@ttu.edu E-mail:ycheng@msu.edu;juntao.huang@ttu.edu;weimath.guo@ttu.edu
基金资助:
This work was supported by the NSF grant DMS-2111383, Air Force Office of Scientific Research FA9550-18-1-0257, and the NSF grant DMS-2011838.

Adaptive Sparse Grid Discontinuous Galerkin Method: Review and Software Implementation

Juntao Huang^1,2, Wei Guo¹, Yingda Cheng³

1. Department of Mathematics and Statistics, Texas Tech University, Lubbock, TX, 79409, USA;
2. Department of Computational Mathematics, Science and Engineering, Michigan State University, East Lansing, MI, 48824, USA;
3. Department of Mathematics, Michigan State University, East Lansing, MI, 48824, USA

Received:2022-11-02 Revised:2023-02-06 Published:2024-04-16
Contact: Yingda Cheng,E-mail:ycheng@msu.edu;Juntao Huang,E-mail:juntao.huang@ttu.edu;Wei Guo,E-mail:weimath.guo@ttu.edu E-mail:ycheng@msu.edu;juntao.huang@ttu.edu;weimath.guo@ttu.edu
Supported by:
This work was supported by the NSF grant DMS-2111383, Air Force Office of Scientific Research FA9550-18-1-0257, and the NSF grant DMS-2011838.

摘要/Abstract

摘要： This paper reviews the adaptive sparse grid discontinuous Galerkin (aSG-DG) method for computing high dimensional partial differential equations (PDEs) and its software implementation. The C++ software package called AdaM-DG, implementing the aSG-DG method, is available on GitHub at https://github.com/JuntaoHuang/adaptive-multiresolution-DG. The package is capable of treating a large class of high dimensional linear and nonlinear PDEs. We review the essential components of the algorithm and the functionality of the software, including the multiwavelets used, assembling of bilinear operators, fast matrix-vector product for data with hierarchical structures. We further demonstrate the performance of the package by reporting the numerical error and the CPU cost for several benchmark tests, including linear transport equations, wave equations, and Hamilton-Jacobi (HJ) equations.

关键词: Adaptive sparse grid, Discontinuous Galerkin, High dimensional partial differential equation, Software development

Abstract: This paper reviews the adaptive sparse grid discontinuous Galerkin (aSG-DG) method for computing high dimensional partial differential equations (PDEs) and its software implementation. The C++ software package called AdaM-DG, implementing the aSG-DG method, is available on GitHub at https://github.com/JuntaoHuang/adaptive-multiresolution-DG. The package is capable of treating a large class of high dimensional linear and nonlinear PDEs. We review the essential components of the algorithm and the functionality of the software, including the multiwavelets used, assembling of bilinear operators, fast matrix-vector product for data with hierarchical structures. We further demonstrate the performance of the package by reporting the numerical error and the CPU cost for several benchmark tests, including linear transport equations, wave equations, and Hamilton-Jacobi (HJ) equations.

Key words: Adaptive sparse grid, Discontinuous Galerkin, High dimensional partial differential equation, Software development

Juntao Huang, Wei Guo, Yingda Cheng. Adaptive Sparse Grid Discontinuous Galerkin Method: Review and Software Implementation[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 501-532.

参考文献

[1] ASGarD-Adaptive Sparse Grid Discretization. https://github.com/project-asgard/asgard. Accessed 18 Oct 2022 (2022)
[2] Alpert, B.K.:A class of bases in L² for the sparse representation of integral operators. SIAM J. Math. Anal. 24(1), 246-262 (1993)
[3] Arnold, D.:An interior penalty finite element method with discontinuous elements. SIAM J. Numer. Anal. 19(4), 742-760 (1982)
[4] Atanasov, A.B., Schnetter, E.:Sparse grid discretizations based on a discontinuous Galerkin method. arXiv:1710.09356 (2017)
[5] Balay, S., Abhyankar, S., Adams, M., Brown, J., Brune, P., Buschelman, K., Dalcin, L., Dener, A., Eijkhout, V., Gropp, W., et al.:PETSc Users Manual, ANL-95/11-Revision 3.11 (2019). http://www.mcs.anl.gov/petsc/petsc-current/docs/manual.pdf
[6] Bellman, R.:Adaptive Control Processes:a Guided Tour, vol. 4. Princeton University Press, Princeton (1961)
[7] Bokanowski, O., Garcke, J., Griebel, M., Klompmaker, I.:An adaptive sparse grid semi-Lagrangian scheme for first order Hamilton-Jacobi Bellman equations. J. Sci. Comput. 55(3), 575-605 (2013)
[8] Bungartz, H.-J., Griebel, M.:Sparse grids. Acta Numer. 13, 147-269 (2004)
[9] Chen, A., Li, F., Cheng, Y.:An ultra-weak discontinuous Galerkin method for Schrödinger equation in one dimension. J. Sci. Comput. 78(2), 772-815 (2019)
[10] Cheng, Y., Shu, C.-W.:A discontinuous Galerkin finite element method for time dependent partial differential equations with higher order derivatives. Math. Comput. 77(262), 699-730 (2008)
[11] Chou, C.-S., Shu, C.-W., Xing, Y.:Optimal energy conserving local discontinuous Galerkin methods for second-order wave equation in heterogeneous media. J. Comput. Phys. 272, 88-107 (2014)
[12] Cockburn, B., Hou, S., Shu, C.-W.:The Runge-Kutta local projection discontinuous Galerkin finite element method for conservation laws IV:the multidimensional case. Math. Comput. 54(190), 545-581 (1990)
[13] D'Azevedo, E., Green, D.L., Mu, L.:Discontinuous Galerkin sparse grids methods for time domain Maxwell's equations. Comput. Phys. Commun. 256, 107412 (2020)
[14] Garcke, J., Griebel, M.:Sparse Grids and Applications. Springer, Berlin (2013)
[15] Gradinaru, V.:Fourier transform on sparse grids:code design and the time dependent Schrödinger equation. Computing 80(1), 1-22 (2007)
[16] Griebel, M.:Sparse grids and related approximation schemes for higher dimensional problems. In:Proceedings of the Conference on Foundations of Computational Mathematics, Santander, Spain (2005)
[17] Griebel, M., Hamaekers, J.:Sparse grids for the Schrödinger equation. ESAIM Math. Modell. Numer. Anal. 41(02), 215-247 (2007)
[18] Guennebaud, G., Jacob, B., et al.:Eigen v3. http://eigen.tuxfamily.org (2010)
[19] Guo, W., Cheng, Y.:A sparse grid discontinuous Galerkin method for high-dimensional transport equations and its application to kinetic simulations. SIAM J. Sci. Comput. 38(6), A3381-A3409 (2016)
[20] Guo, W., Cheng, Y.:An adaptive multiresolution discontinuous Galerkin method for time-dependent transport equations in multidimensions. SIAM J. Sci. Comput. 39(6), A2962-A2992 (2017)
[21] Guo, W., Huang, J., Tao, Z., Cheng, Y.:An adaptive sparse grid local discontinuous Galerkin method for Hamilton-Jacobi equations in high dimensions. J. Comput. Phys. 436, 110294 (2021)
[22] Huang, J., Cheng, Y.:An adaptive multiresolution discontinuous Galerkin method with artificial viscosity for scalar hyperbolic conservation laws in multidimensions. SIAM J. Sci. Comput. 42(5), A2943-A2973 (2020)
[23] Huang, J., Liu, Y., Guo, W., Tao, Z., Cheng, Y.:An adaptive multiresolution interior penalty discontinuous Galerkin method for wave equations in second order form. J. Sci. Comput. 85(1), 1-31 (2020)
[24] Huang, J., Liu, Y., Liu, Y., Tao, Z., Cheng, Y.:A class of adaptive multiresolution ultra-weak discontinuous Galerkin methods for some nonlinear dispersive wave equations. SIAM J. Sci. Comput. 44(2), A745-A769 (2022)
[25] Pareschi, L., Russo, G.:Implicit-explicit Runge-Kutta schemes and applications to hyperbolic systems with relaxation. J. Sci. Comput. 25(1), 129-155 (2005)
[26] Pflüger, D.:Spatially Adaptive Sparse Grids for High-Dimensional Problems. Verlag Dr. Hut, München (2010)
[27] Schwab, C., Süli, E., Todor, R.:Sparse finite element approximation of high-dimensional transport-dominated diffusion problems. ESAIM Math. Modell. Numer. Anal. 42(05), 777-819 (2008)
[28] Shen, J., Wang, L.-L.:Sparse spectral approximations of high-dimensional problems based on hyperbolic cross. SIAM J. Numer. Anal. 48(3), 1087-1109 (2010)
[29] Shen, J., Yu, H.:Efficient spectral sparse grid methods and applications to high-dimensional elliptic problems. SIAM J. Sci. Comput. 32(6), 3228-3250 (2010)
[30] Shu, C.-W., Osher, S.:Efficient implementation of essentially non-oscillatory shock-capturing schemes. J. Comput. Phys. 77(2), 439-471 (1988)
[31] Tao, Z., Huang, J., Liu, Y., Guo, W., Cheng, Y.:An adaptive multiresolution ultra-weak discontinuous Galerkin method for nonlinear Schrödinger equations. Commun. Appl. Math. Comput. 4(1), 60-83 (2022)
[32] Tao, Z., Jiang, Y., Cheng, Y.:An adaptive high-order piecewise polynomial based sparse grid collocation method with applications. J. Comput. Phys. 433, 109770 (2021)
[33] Wang, Z., Tang, Q., Guo, W., Cheng, Y.:Sparse grid discontinuous Galerkin methods for high-dimensional elliptic equations. J. Comput. Phys. 314, 244-263 (2016)
[34] Wanner, G., Hairer, E.:Solving Ordinary Differential Equations I, vol. 375. Springer, Berlin (1996)
[35] Yan, J., Osher, S.:A local discontinuous Galerkin method for directly solving Hamilton-Jacobi equations. J. Comput. Phys. 230(1), 232-244 (2011)
[36] Zenger, C.:Sparse grids. In:Parallel Algorithms for Partial Differential Equations, Proceedings of the Sixth GAMM-Seminar, vol. 31 (1990)

Adaptive Sparse Grid Discontinuous Galerkin Method: Review and Software Implementation

Adaptive Sparse Grid Discontinuous Galerkin Method: Review and Software Implementation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	Maohui Lyu, Vrushali A. Bokil, Yingda Cheng, Fengyan Li. Energy Stable Nodal DG Methods for Maxwell’s Equations of Mixed-Order Form in Nonlinear Optical Media[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 30-63.
[2]	Fangyao Zhu, Juntao Huang, Yang Yang. Bound-Preserving Discontinuous Galerkin Methods with Modified Patankar Time Integrations for Chemical Reacting Flows[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 190-217.
[3]	Xuechun Liu, Haijin Wang, Jue Yan, Xinghui Zhong. Superconvergence of Direct Discontinuous Galerkin Methods: Eigen-structure Analysis Based on Fourier Approach[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 257-278.
[4]	Mengjiao Jiao, Yan Jiang, Mengping Zhang. A Provable Positivity-Preserving Local Discontinuous Galerkin Method for the Viscous and Resistive MHD Equations[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 279-310.
[5]	Bo Dong, Wei Wang. Numerical Investigations on the Resonance Errors of Multiscale Discontinuous Galerkin Methods for One-Dimensional Stationary Schrödinger Equation[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 311-324.
[6]	Wei Zheng, Yan Xu. High-Order Decoupled and Bound Preserving Local Discontinuous Galerkin Methods for a Class of Chemotaxis Models[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 372-398.
[7]	Wei Guo, Jannatul Ferdous Ema, Jing-Mei Qiu. A Local Macroscopic Conservative (LoMaC) Low Rank Tensor Method with the Discontinuous Galerkin Method for the Vlasov Dynamics[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 550-575.
[8]	Ruihan Guo, Yinhua Xia. Arbitrary High-Order Fully-Decoupled Numerical Schemes for Phase-Field Models of Two-Phase Incompressible Flows[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 625-657.
[9]	Joseph Hunter, Zheng Sun, Yulong Xing. Stability and Time-Step Constraints of Implicit-Explicit Runge-Kutta Methods for the Linearized Korteweg-de Vries Equation[J]. Communications on Applied Mathematics and Computation, 2024, 6(1): 658-687.
[10]	Changpin Li, Dongxia Li, Zhen Wang. L1/LDG Method for the Generalized Time-Fractional Burgers Equation in Two Spatial Dimensions[J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1299-1322.
[11]	Kiera van der Sande, Daniel Appelö, Nathan Albin. Fourier Continuation Discontinuous Galerkin Methods for Linear Hyperbolic Problems[J]. Communications on Applied Mathematics and Computation, 2023, 5(4): 1385-1405.
[12]	Johannes Markert, Gregor Gassner, Stefanie Walch. A Sub-element Adaptive Shock Capturing Approach for Discontinuous Galerkin Methods[J]. Communications on Applied Mathematics and Computation, 2023, 5(2): 679-721.
[13]	Shima Baharlouei, Reza Mokhtari, Nabi Chegini. A Stable Numerical Scheme Based on the Hybridized Discontinuous Galerkin Method for the Ito-Type Coupled KdV System[J]. Communications on Applied Mathematics and Computation, 2022, 4(4): 1351-1373.
[14]	Xiaozhou Li. How to Design a Generic Accuracy-Enhancing Filter for Discontinuous Galerkin Methods[J]. Communications on Applied Mathematics and Computation, 2022, 4(3): 759-782.
[15]	Lorenzo Botti, Daniele A. Di Pietro. p-Multilevel Preconditioners for HHO Discretizations of the Stokes Equations with Static Condensation[J]. Communications on Applied Mathematics and Computation, 2022, 4(3): 783-822.