Adaptive Sparse Grid Discontinuous Galerkin Method: Review and Software Implementation

doi:10.1007/s42967-023-00268-8

Abstract

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.

TrendMD

References

[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)