Analysis of linear difference schemes in the sparse grid combination technique

ISSN： 1464-3642

Source： IMA Journal of Numerical Analysis, Vol.33, Iss.2, 2013-04, pp. : 544-581

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Sparse grids (Zenger, C. (1990) Sparse grids. Parallel Algorithms for Partial Differential Equations (W. Hackbusch ed.) Notes on Numerical Fluid Dynamics 31. Proceedings of the Sixth GAMM-Seminar; Bungartz, H.-J. & Griebel, M. (2004) Sparse grids. Acta Numer., 13, 1123.) are tailored to the approximation of smooth high-dimensional functions. On a d-dimensional tensor product space, the number of grid points is N (h¹ log h^d1), where h is a mesh parameter. The so-called combination technique, based on hierarchical decomposition and extrapolation, requires specific multivariate error expansions of the discretization error on Cartesian grids to hold. We derive such error expansions for linear difference schemes through an error correction technique of semi-discretizations. We obtain overall error formulae of the type (h^p log h^d1) and analyse the convergence, with its dependence on dimension and smoothness, by examples of linear elliptic and parabolic problems, with numerical illustrations in up to eight dimensions.