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(h^{2}). 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(h^{2}(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(h^{2}log 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).