A Generalized Spatially Adaptive Sparse Grid Combination Technique with Dimension-wise Refinement

Today, high-dimensional calculations can be found in almost all scientific disciplines. The application of machine learning and uncertainty quantification methods are common examples where high-dimensional problems appear. Typically, these problems are computationally expensive or even infeasible on current machines due to the curse of dimensionality. The sparse grid combination technique is one method to mitigate this effect, but it still does not generate optimal grids for many application scenarios. In such cases, adaptivity strategies are applied to further optimize the grid generation. Generally, adaptive grid generation strategies can be be classified as spatially or dimensionally adaptive. One of the most prominent examples is the dimension-adaptive combination technique, which is easy to implement and suitable for cases where dimensions contribute in different magnitudes to the accuracy of the solution. Unfortunately, spatial adaptivity is not possible in the standard combination technique due to the required regular structure of the grids. We therefore propose a new algorithmic variant of the combination technique that is based on the combination of rectilinear grids which can adapt themselves locally to the target function using 1-dimensional refinements. We further increase the efficiency by adjusting point levels with tree rebalancing. Results for numerical quadrature and interpolation show that we can significantly improve upon the standard combination technique and compete with or even surpass common spatially adaptive implementations with sparse grids. At the same time our method keeps the black-box property of the combination technique which makes it possible to apply it to black-box solvers.