Theory of the sparse grid combination technique

Abstract

In real-world applications mathematical models often involve more than one vari­able. For example, a problem in physics may involve the 3 spatial variables-time, velocity and momentum. A problem in disease modelling may involve time, the population size, the age distribution and the infectivity factor. In practice, when we seek a computational solution to these multi-dimensional problems, we en­counter the so-called 'curse of dimensionality." The curse of dimensionality says that the amount of resources (time and computational memory) needed to solve a problem grows exponentially with the number of dimensions. In applications, problems of more than 5 or 6 dimensions become impractical to solve. The sparse grid combination technique is an algorithm designed to tackle the curse of dimensionality. In 1992, the convergence theory for the technique was shown for the Laplace's Equation. Since then, the technique has b n widely applied to other problems. Nevertheless, the success of technique is only par­tially understood. In practice, the method is u ed as a black-box to solve multi­dimensional problems. In this work, we generalise the theory of the combination technique to a large class of linear projections on tensor product Hilbert paces. The result is shown for an arbitrary number of dimensions. This significantly extends our understanding of the combination technique. Moreover, we study combination technique which u e different combination grids compared to the classical formula. We establish the theoretical framework for this generalisation and develop a general error analysis for this approach. Finally, we study combination techniques with different combination coeffi­cients. This approach was used in the Opticom method for orthogonal projec­tions. We generalise the technique to more generic problems. Using this general­isation, we prove a convergence result for a new, iterative combination technique for convex minimisation. Numerical experiments confirm our theoretical results.