Adaptive Sparse Grid Discontinuous Galerkin Method: Review and Software Implementation

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.

Keywords

Adaptive sparse grid / Discontinuous Galerkin / High dimensional partial differential equation / Software development

References

[1.] ASGarD—Adaptive Sparse Grid Discretization. https://github.com/project-asgard/asgard. Accessed 18 Oct 2022 (2022)

[2.] Alpert BK. A class of bases in L \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L$$\end{document} 2 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$^2$$\end{document} for the sparse representation of integral operators. SIAM J. Math. Anal., 1993, 24(1): 246-262,

[3.] Arnold D. An interior penalty finite element method with discontinuous elements. SIAM J. Numer. Anal., 1982, 19(4): 742-760,

[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., 2013, 55(3): 575-605,

[8.] Bungartz H-J, Griebel M. Sparse grids. Acta Numer., 2004, 13: 147-269,

[9.] Chen A, Li F, Cheng Y. An ultra-weak discontinuous Galerkin method for Schrödinger equation in one dimension. J. Sci. Comput., 2019, 78(2): 772-815,

[10.] Cheng Y, Shu C-W. A discontinuous Galerkin finite element method for time dependent partial differential equations with higher order derivatives. Math. Comput., 2008, 77(262): 699-730,

[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., 2014, 272: 88-107,

[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 DL, Mu L. Discontinuous Galerkin sparse grids methods for time domain Maxwell’s equations. Comput. Phys. Commun., 2020, 256,

[14.] Garcke J, Griebel M. . Sparse Grids and Applications, 2013 Berlin Springer,

[15.] Gradinaru V. Fourier transform on sparse grids: code design and the time dependent Schrödinger equation. Computing, 2007, 80(1): 1-22,

[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., 2007, 41(02): 215-247,

[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., 2016, 38(6): A3381-A3409,

[20.] Guo W, Cheng Y. An adaptive multiresolution discontinuous Galerkin method for time-dependent transport equations in multidimensions. SIAM J. Sci. Comput., 2017, 39(6): A2962-A2992,

[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., 2020, 42(5): A2943-A2973,

[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., 2020, 85(1): 1-31,

[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., 2022, 44(2): A745-A769,

[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, 2010 München Verlag Dr. Hut

[27.] Schwab C, Süli E, Todor R. Sparse finite element approximation of high-dimensional transport-dominated diffusion problems. ESAIM Math. Modell. Numer. Anal., 2008, 42(05): 777-819,

[28.] Shen J, Wang L-L. Sparse spectral approximations of high-dimensional problems based on hyperbolic cross. SIAM J. Numer. Anal., 2010, 48(3): 1087-1109,

[29.] Shen J, Yu H. Efficient spectral sparse grid methods and applications to high-dimensional elliptic problems. SIAM J. Sci. Comput., 2010, 32(6): 3228-3250,

[30.] Shu C-W, Osher S. Efficient implementation of essentially non-oscillatory shock-capturing schemes. J. Comput. Phys., 1988, 77(2): 439-471,

[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., 2022, 4(1): 60-83,

[32.] Tao Z, Jiang Y, Cheng Y. An adaptive high-order piecewise polynomial based sparse grid collocation method with applications. J. Comput. Phys., 2021, 433,

[33.] Wang Z, Tang Q, Guo W, Cheng Y. Sparse grid discontinuous Galerkin methods for high-dimensional elliptic equations. J. Comput. Phys., 2016, 314: 244-263,

[34.] Wanner G, Hairer E. . Solving Ordinary Differential Equations I, 1996 Berlin Springer

[35.] Yan J, Osher S. A local discontinuous Galerkin method for directly solving Hamilton-Jacobi equations. J. Comput. Phys., 2011, 230(1): 232-244,

[36.] Zenger, C.: Sparse grids. In: Parallel Algorithms for Partial Differential Equations, Proceedings of the Sixth GAMM-Seminar, vol. 31 (1990)

Funding

National Science Foundation(DMS-2011838); U.S. Air Force(FA9550-18-1-0257)