Sparse Grids

We consider the solution of initial-boundary value problems of partial differential equations on sparse grid discretizations, both parabolic and hyperbolic problems. Sparse grids can be constructed from tensor products of one dimensional spaces, where specific parts of the space are cut off. Based on the hierarchic basis functions (or other pre-wavelet bases), products of functions with a support less than tol are cut off. This is depicted on the right hand side.

The sparse grid construction is related to `hyperbolic crosspoints' and other approximation schemes. We are now interested in the discretization of PDEs. Besides the Galerkin approach (FEM) and the `combination technique' based on multivariate extrapolation, we propose a finite differcence type of discretization. It is based on dimensional splitting and the (nodal to) hierarchical basis transform H. Each differential operator Dj along a direction j is discretized with finite differences. It is combined with a hierarchical basis transform and back-transform along all directions but the direction of interest j . The global differential operator reads .

A typical stiffness matrix looks like this:

It is not sparse, but a matrix multiply can be implemented in linear time O(n).

Time discretizations

There are several possibilities for the discretization of time dependent PDEs. One can split the problem into an initial value problem in time and a sequence of boundary value problems in space

or one can discretize the space-time domain at once.

The latter strategy usually is prohibitive because the large number of unknowns to be stored. However, in the presence of sparse grids the additional time discretization is not that expensive. Note that the number of operations is comparable both for time-stepping and for space-time discretizations. A finite difference discretization of the initial-boundary value problem in space-time may look like this

Problems with large time-intervals or of unknown time-length can be discretized by macro time-stepping

Heat Conduction, space-time

A model problem for parabolic PDEs is the heat conduction equation

which can be discretized by finite differences on a regular grid as

The discretiztion is first order, implict in time (backward Euler = upwind) and second order in space. The corresponding sparse grid finite differences version reads as

along with piecewise constant hierarchical basis transform in time direction, forward in time [0 1 1] instead of linear hierarchical basis transform [.5 1 .5]. We consider the one-dimensional case with zero boundary value conditions, zero source and a step function as initial values The solution is space-time looks like this:

Now we use a-posteriori error indicators and grid adaptivity to adapt the grid to the solution. In order to have second order accuracy in space, we have to modify the finite difference stencils

The solution of the two dimensional heat equation with an L-shaped step as initial conditions in three dimensional space-time is depicted in the following pictures:

The solution is shown at different time steps t=0, .025, .05, .075, .1 .

The solution of the three dimensional heat equation with an L-shaped step as initial conditions s depicted in the following pictures at t=0 and t=.1.

Oblique Advection, space-time

We consider the solution of scalar hyperbolic conservation laws, which can be written in conservative form as .
As a model problem we look at the linear oblique advection problem , which can be re-written in space-time as . The finite difference sparse grid discretization is

The solution of the one dimensional problem in two dimensional space-time for a smooth and for a non-smooth initial value is shown in the next pictures.

The l1 convergence rates demonstrate the better ratio of degress of freedom (N) to error for the sparse grid approximation compared to a regular grid. Further improvements can be obtained by adaptive grid refinement.

Burger's equation, time-stepping

We consider the solution of hyperbolic conservation laws by an explicit time-stepping algorithm. As a model problem two-dimensional Burger's equation

with a centered non-staggered Lax-Friedrichs scheme is solved.

The construction of the corresponding sparse grid finite difference scheme requires a basis-free formulation. We pre-evalute the non-linear flux function f, before we apply a basis transform.

By dimensional splitting and the appropriate hierarchical basis transforms we arrive at the sparse grid version of the Lax-Friedrichs scheme.

The solution of two-dimensional Burger's equation for a smooth (pre-shock) and a non-smooth initial value are shown in the next pictures.