Title | Finite Difference Schemes on Sparse Grids for Time
Dependent Problems |

Participant | Gerhard Zumbusch |

Key words | Sparse Grids, Hyperbolic Crosspoints, Tensor Product Approximation, Finite Differences, Parabolic Problems, Hyperbolic Conservation Laws, Central Difference Schemes, Space-Time Discretization, Waveform Relaxation |

Description |
## Sparse GridsWe 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 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 A typical stiffness matrix looks like this: It is not sparse, but a matrix multiply can be implemented in linear
time ## Time discretizationsThere 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-timeA 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-timeWe 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-steppingWe 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 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. |

Bibliography |
H.G. Roos, M. Stynes, L. Tobiska, Numerical Methods for Singularly
Perturbed Differential Equations - Convection-Diffusion and Flow Problems,
Springer, 1996.M. Griebel, Adaptive sparse grid multilevel methods for elliptic
PDEs based on finite differences, Computing, 1998.R. Balder, U. Rüde, S. Schneider, C. Zenger, Sparse
grid and extrapolation methods for parabolic problems, International
Conference on Computational Methods in Water Resources X, Heidelberg, July
19-22, 1994, p.1383-1392, Eds.: Peters, A. et. al., Dordrecht, Kluwer Academic
Publishers.M. Griebel, G. Zumbusch, , Proceedings
of Seventh International Conference on Hyperbolic Problems, Theory, Numerics,
Applications, Birkhäuser, 1998Adaptive
Sparse Grids for Hyperbolic Conservation Laws.T. Schiekofer, G. Zumbusch, , Proceedings
of the 14th GAMM-Seminar Kiel on Concepts of Numerical Software, editor:
W. Hackbusch, G. Wittum, Notes on Numerical Fluid Mechanics, Vieweg, 1998
Software
Concepts of a Sparse Grid Finite Difference Code. G. Zumbusch, , A
Sparse Grid PDE Solver. Advances in Software Tools for
Scientific Computing (Proceedings SciTools '98), editor: H. P. Langtangen, A. M. Bruaset,
E. Quak,
Springer, 2000, chapter 4 in Lecture Notes in Computational Science and
Engineering 10, pp. 133-178 |

Related projects |
Parallel Adaptive Sparse Grids |

In cooperation with | SFB 256 "Nonlinear Partial Differential Equations" |