|Title||Finite Difference Schemes on Sparse Grids for Time Dependent Problems|
|Key words||Sparse Grids, Hyperbolic Crosspoints, Tensor Product Approximation, Finite Differences, Parabolic Problems, Hyperbolic Conservation Laws, Central Difference Schemes, Space-Time Discretization, Waveform Relaxation|
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).
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 .
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.
|In cooperation with||SFB 256 "Nonlinear Partial Differential Equations"|