×

Sparse grid discontinuous Galerkin methods for high-dimensional elliptic equations. (English) Zbl 1349.65636

Summary: This paper constitutes our initial effort in developing sparse grid discontinuous Galerkin (DG) methods for high-dimensional partial differential equations (PDEs). Over the past few decades, DG methods have gained popularity in many applications due to their distinctive features. However, they are often deemed too costly because of the large degrees of freedom of the approximation space, which are the main bottleneck for simulations in high dimensions. In this paper, we develop sparse grid DG methods for elliptic equations with the aim of breaking the curse of dimensionality. Using a hierarchical basis representation, we construct a sparse finite element approximation space, reducing the degrees of freedom from the standard \(O(h^{- d})\) to \(O(h^{- 1} | \log_2 h |^{d - 1})\) for \(d\)-dimensional problems, where \(h\) is the uniform mesh size in each dimension. Our method, based on the interior penalty (IP) DG framework, can achieve accuracy of \(O(h^k | \log_2 h |^{d - 1})\) in the energy norm, where \(k\) is the degree of polynomials used. Error estimates are provided and confirmed by numerical tests in multi-dimensions.

MSC:

65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs

References:

[1] Achatz, S., Higher order sparse grid methods for elliptic partial differential equations with variable coefficients, Computing, 71, 1, 1-15 (2003) · Zbl 1030.65114
[2] Alpert, B., A class of bases in L̂2 for the sparse representation of integral operators, SIAM J. Math. Anal., 24, 1, 246-262 (1993) · Zbl 0764.42017
[3] Alpert, B.; Beylkin, G.; Gines, D.; Vozovoi, L., Adaptive solution of partial differential equations in multiwavelet bases, J. Comput. Phys., 182, 1, 149-190 (2002) · Zbl 1015.65046
[4] Archibald, R.; Fann, G.; Shelton, W., Adaptive discontinuous Galerkin methods in multiwavelets bases, Appl. Numer. Math., 61, 7, 879-890 (2011) · Zbl 1216.65126
[5] Arnold, D., An interior penalty finite element method with discontinuous elements, SIAM J. Numer. Anal., 19, 4, 742-760 (1982) · Zbl 0482.65060
[6] Arnold, D.; Brezzi, F.; Cockburn, B.; Marini, L., Unified analysis of discontinuous Galerkin methods for elliptic problems, SIAM J. Numer. Anal., 39, 1749-1779 (2002) · Zbl 1008.65080
[7] Babenko, K., Approximation of periodic functions of many variables by trigonometric polynomials, Dokl. Akad. Nauk SSSR, 132, 2, 247-250 (1960) · Zbl 0099.28302
[8] Baker, G., Finite element methods for elliptic equations using nonconforming elements, Math. Comput., 31, 137, 45-59 (1977) · Zbl 0364.65085
[9] Bassi, F.; Rebay, S., A high-order accurate discontinuous finite element method for the numerical solution of the compressible Navier-Stokes equations, J. Comput. Phys., 131, 267-279 (1997) · Zbl 0871.76040
[10] Baszenski, G.; Delvos, F.-J.; Jester, S., Blending Approximations with Sine Functions, Numerical Methods in Approximation Theory, vol. 9, 1-19 (1992), Springer · Zbl 0822.42008
[11] Bellman, R., Adaptive Control Processes: A Guided Tour, vol. 4 (1961), Princeton University Press: Princeton University Press Princeton · Zbl 0103.12901
[12] Bungartz, H.-J., A multigrid algorithm for higher order finite elements on sparse grids, Electron. Trans. Numer. Anal., 6, 63-77 (1997) · Zbl 0903.65087
[13] Bungartz, H.-J., Finite Elements of Higher Order on Sparse Grids (1998), Shaker
[14] Bungartz, H.-J.; Dornseifer, T., Sparse grids: recent developments for elliptic partial differential equations, (Multigrid Methods v (1998), Springer), 45-70 · Zbl 0927.65134
[15] Bungartz, H.-J.; Griebel, M., Sparse grids, Acta Numer., 13, 147-269 (2004) · Zbl 1118.65388
[16] Calle, J.; Devloo, P.; Gomes, S., Wavelets and adaptive grids for the discontinuous Galerkin method, Numer. Algorithms, 39, 1-3, 143-154 (2005) · Zbl 1068.65118
[17] Castillo, P.; Cockburn, B.; Perugia, I.; Schötzau, D., An a priori error analysis of the local discontinuous Galerkin method for elliptic problems, SIAM J. Numer. Anal., 38, 5, 1676-1706 (2000) · Zbl 0987.65111
[18] Ciarlet, P., The Finite Element Method for Elliptic Problems (1975), North-Holland: North-Holland Amsterdam
[19] Cockburn, B.; Kanschat, G.; Perugia, I.; Schötzau, D., Superconvergence of the local discontinuous Galerkin method for elliptic problems on cartesian grids, SIAM J. Numer. Anal., 39, 1, 264-285 (2001) · Zbl 1041.65080
[20] Cockburn, B.; Li, F.; Shu, C.-W., Locally divergence-free discontinuous Galerkin methods for the Maxwell equations, J. Comput. Phys., 194, 588-610 (2004) · Zbl 1049.78019
[21] Cockburn, B.; Shu, C.-W., The local discontinuous Galerkin method for time-dependent convection-diffusion systems, SIAM J. Numer. Anal., 35, 6, 2440-2463 (1998) · Zbl 0927.65118
[22] Dawson, C.; Sun, S.; Wheeler, M., Compatible algorithms for coupled flow and transport, Comput. Methods Appl. Mech. Eng., 193, 23, 2565-2580 (2004) · Zbl 1067.76565
[23] Delvos, F.-J., \(d\)-variate Boolean interpolation, J. Approx. Theory, 34, 2, 99-114 (1982) · Zbl 0504.41004
[24] Douglas, J.; Dupont, T., Interior penalty procedures for elliptic and parabolic Galerkin methods, (Computing Methods in Applied Sciences (1976), Springer), 207-216
[25] Garcke, J.; Griebel, M., Sparse Grids and Applications (2013), Springer
[26] Gerhard, N.; Müller, S., Adaptive multiresolution discontinuous Galerkin schemes for conservation laws: multi-dimensional case, Comput. Appl. Math., 1-29 (2013)
[27] Gerstner, T.; Griebel, M., Numerical integration using sparse grids, Numer. Algorithms, 18, 3-4, 209-232 (1998) · Zbl 0921.65022
[28] Gradinaru, V., Fourier transform on sparse grids: code design and the time dependent Schrödinger equation, Computing, 80, 1, 1-22 (2007) · Zbl 1117.65137
[29] Griebel, M., A parallelizable and vectorizable multi-level algorithm on sparse grids, (Hackbusch, W., Parallel Algorithms for Partial Differential Equations. Parallel Algorithms for Partial Differential Equations, Notes Numer. Fluid Mech., vol. 31 (1991)), 94-100 · Zbl 0741.65090
[30] Griebel, M., Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences, Computing, 61, 2, 151-179 (1998) · Zbl 0918.65078
[31] Griebel, M., Sparse grids and related approximation schemes for higher dimensional problems, (Proceedings of the Conference on Foundations of Computational Mathematics. Proceedings of the Conference on Foundations of Computational Mathematics, Santander, Spain (2005))
[32] Griebel, M.; Hamaekers, J., Sparse grids for the Schrödinger equation, Math. Model. Numer. Anal., 41, 02, 215-247 (2007) · Zbl 1145.65096
[33] Griebel, M.; Oswald, P., Tensor product type subspace splittings and multilevel iterative methods for anisotropic problems, Adv. Comput. Math., 4, 1, 171-206 (1995) · Zbl 0826.65099
[34] Griebel, M.; Zenger, C.; Zimmer, S., Multilevel Gauss-Seidel-algorithms for full and sparse grid problems, Computing, 50, 2, 127-148 (1993) · Zbl 0771.65084
[35] Griebel, M.; Zumbusch, G., Adaptive sparse grids for hyperbolic conservation laws, (Hyperbolic Problems: Theory, Numerics, Applications (1999), Springer), 411-422 · Zbl 0929.65075
[36] Haar, A., Zur theorie der orthogonalen funktionensysteme, Math. Ann., 69, 3, 331-371 (1910) · JFM 41.0469.03
[37] Hemker, P., Sparse-grid finite-volume multigrid for 3D-problems, Adv. Comput. Math., 4, 1, 83-110 (1995) · Zbl 0826.65100
[38] Hovhannisyan, N.; Müller, S.; Schäfer, R., Adaptive multiresolution discontinuous Galerkin schemes for conservation laws, Math. Comput., 83, 285, 113-151 (2014) · Zbl 1282.65118
[39] Iacono, F.; May, F.; Müller, S.; Schäfer, R., A high-order discontinuous Galerkin discretization with multiwavelet-based grid adaptation for compressible flows (2011), RWTH Aachen, AICES preprint AICES-2011/08-1
[40] Liem, C.; Lü, T.; Shih, T., The Splitting Extrapolation Method: A New Technique in Numerical Solution of Multidimensional Problems, vol. 7 (1995), World Scientific · Zbl 0875.65002
[41] Ma, X.; Zabaras, N., An adaptive hierarchical sparse grid collocation algorithm for the solution of stochastic differential equations, J. Comput. Phys., 228, 8, 3084-3113 (2009) · Zbl 1161.65006
[42] Mulder, W., A new multigrid approach to convection problems, J. Comput. Phys., 83, 2, 303-323 (1989) · Zbl 0672.76087
[43] Naik, N.; Van Rosendale, J., The improved robustness of multigrid elliptic solvers based on multiple semicoarsened grids, SIAM J. Numer. Anal., 30, 1, 215-229 (1993) · Zbl 0774.65081
[44] Nobile, F.; Tempone, R.; Webster, C., A sparse grid stochastic collocation method for partial differential equations with random input data, SIAM J. Numer. Anal., 46, 5, 2309-2345 (2008) · Zbl 1176.65137
[45] Oden, J.; Babuška, I.; Baumann, C., A discontinuous hp finite element method for diffusion problems, J. Comput. Phys., 146, 2, 491-519 (1998) · Zbl 0926.65109
[46] Pflaum, C., A multilevel algorithm for the solution of second order elliptic differential equations on sparse grids, Numer. Math., 79, 1, 141-155 (1998) · Zbl 0898.65069
[47] Rivière, B.; Wheeler, M.; Girault, V., A priori error estimates for finite element methods based on discontinuous approximation spaces for elliptic problems, SIAM J. Numer. Anal., 39, 3, 902-931 (2001) · Zbl 1010.65045
[48] Schwab, C.; Süli, E.; Todor, R., Sparse finite element approximation of high-dimensional transport-dominated diffusion problems, Math. Model. Numer. Anal., 42, 05, 777-819 (2008) · Zbl 1159.65094
[49] 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) · Zbl 1215.65179
[50] 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) · Zbl 1233.65094
[51] Smolyak, S., Quadrature and interpolation formulas for tensor products of certain classes of functions, Dokl. Akad. Nauk SSSR, 4, 240-243 (1963) · Zbl 0202.39901
[52] Temlyakov, V., Approximations of functions with bounded mixed derivative, Tr. Mat. Inst. Steklova, 178, 3-113 (1986) · Zbl 0625.41028
[53] Vuik, M.; Ryan, J., Multiwavelet troubled-cell indicator for discontinuity detection of discontinuous Galerkin schemes, J. Comput. Phys., 270, 138-160 (2014) · Zbl 1349.65490
[54] Wang, W.; Shu, C.-W., The WKB local discontinuous Galerkin method for the simulation of Schrödinger equation in a resonant tunneling diode, J. Sci. Comput., 40, 1-3, 360-374 (2009) · Zbl 1203.65119
[55] Wang, Z., Discontinuous Galerkin methods for Hamilton-Jacobi equations and high-dimensional elliptic equations (2015), Michigan State University, PhD thesis
[56] Wheeler, M., An elliptic collocation-finite element method with interior penalties, SIAM J. Numer. Anal., 15, 1, 152-161 (1978) · Zbl 0384.65058
[57] Xiu, D., Efficient collocational approach for parametric uncertainty analysis, Commun. Comput. Phys., 2, 2, 293-309 (2007) · Zbl 1164.65302
[58] Xiu, D.; Hesthaven, J., High-order collocation methods for differential equations with random inputs, SIAM J. Sci. Comput., 27, 3, 1118-1139 (2005) · Zbl 1091.65006
[59] Yuan, L.; Shu, C.-W., Discontinuous Galerkin method based on non-polynomial approximation spaces, J. Comput. Phys., 218, 1, 295-323 (2006) · Zbl 1104.65094
[60] Zenger, C., Sparse grids, (Parallel Algorithms for Partial Differential Equations, Proceedings of the Sixth GAMM-Seminar, vol. 31 (1990)) · Zbl 0763.65091
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.