Error Analysis for Sparse-Grid Recombination

Boris Lastdrager
Barry Koren
CWI, The Netherlands


Sparse grids were introduced in 1990 by Zenger [1], in order to significantly reduce the number of degrees of freedom that describe the solution to a discretized partial differential equation, while causing only a marginal increase in representation error relative to the standard discretization. Representing a solution as a piecewise d-linear function on a conventional d-dimensional grid of mesh width h requires O(h-d) degrees of freedom, while the representation error is O(h2). The representation as a linear combination of hierarchical basis functions on a sparse grid requires only O(h-1(log h-1)d-1) degrees of freedom. In fact, this is only a one-dimensional complexity, while the approximation error is O(h2(log h-1)d-1), which is only slightly worse than for the conventional, full-grid representation. In 1992, Griebel, Schneider and Zenger [2] showed that, for two and three dimensions, the sparse-grid complexity and representation error can also be achieved by the so-called combination technique. This technique combines O((log h-1)d-1) representations on conventional grids of different mesh widths in different directions, each containing O(h-1) points into a representation on the conventional, full grid. In the current work, the asymptotic representation error for the combination technique is shown to be O(h2log h-1), for the two-dimensional case. The current derivation does not involve the use of hierarchical basis functions. Instead, direct analyses are given of the steps that comprise the combination technique. Numerical results that confirm the analyses will be presented.

The work is directed towards the numerical solution of large-scale transport problems, governed by systems of partial differential equations of the advection-diffusion-reaction type. These equations play a prominent role in the mathematical modeling of pollution of, e.g, atmospheric air, surface water and ground water. The three-dimensional nature of these models and the necessity of modeling transport and chemical reactions between different species over long time spans, requires very efficient algorithms. When using full-grid methods, computer capacity (computing time and memory) is and will probably remain to be a severe limiting factor. Sparse-grid methods hold out the promise of alleviating these limitations.


[1] C. Zenger, Sparse grids, in: W. Hackbusch, ed., Notes on Numerical Fluid Mechanics, 31, 241-251 (Vieweg, Braunschweig, 1990).

[2] M. Griebel, M. Schneider and C. Zenger, A combination technique for the solution of sparse grid problems, in: R. Beauwens and P. de Groen, eds., Iterative Methods in Linear Algebra, 263-281 (North-Holland, Amsterdam, 1992).