Title  Finitedifferences on Sparse Grids for the Solution of Partial Differential Integrations 
Participiants  Thomas Schiekofer Michael Griebel 
Keywords  Finite Differences, Partial Differential Equations, Sparse Grids 
Description 
Sparse GridsWe consider the solution of elliptic and parabolic partial differential equations on the domain and together with appropriate boundary conditions, respectively. Usually, the discretization of these equations on the respective domains is done by the use of full grids with equidistant meshwidths in each coordinate direction. Using the piecewise linear hierarchical basis, a full grid can be obtained by taking a rectangular scheme of the infinite tableau of subspaces into account as it can be seen on the left side of Figure 1. A discussion of the properties of the subspaces together with a comparison of accuracy vs. effort for each subspace (a detailed discussion can be found in [1]) leads to the result, that it is more reasonable to use a triangular scheme as indicated on the right side of Figure 1 which leads to a sparse grid instead of taking a rectangular scheme into account.
Figure 2 shows this procedure in the twodimensional case where a derivative in xdirection is considered. A more detailed description of this scheme can be found in [2] and [4].
With this is mind, D_{j}^{SG} simply reads . If D_{i}^{SG} is considered to be a discretization for the second derivative, the expression
represents the Laplacian operator. Note that, the discretized differential operators lead to nonsymmetric matrices even for selfadjoint differential operators like the Laplacian. Hence, we need an iterative solver that can handle systems of linear equations with nonsymmetric matrices. The solver we implemented therefore is the preconditioned BiCGstab method. Although the discretization matrices are not sparse, a matrixvector multiplication can be implemented in O(N) where N denotes the number of grid points. In the following, some numerical examples are presented. Details about discretizations, preconditioning, properties of the discretization matrices, proofs of consistency and so on can be found in [4]. There, more numerical examples including also the Navier Stokes equations can be obtained.
elliptic PDE'sAs a first example, we consider a Laplace equation on the unit square with the solution
and right hand side f=0. Additionally, Dirichlet conditions are imposed on the boundary. The numerical results can be seen in Table 1 where the error measured in the maximum norm and the L_{2}norm is shown. Figure 2 shows the corresponding convergence rates. Here, also the L_{1}norm as well as a pointwise measured error can be obtained.
with b=(2,3) and c=1. The solution of this problem is chosen to be
together with the apropriate right hand side. Again, Dirichlet boundary conditions are imposed. Table 2 shows the numerical results where again the errors measured in the maximum norm and the L_{2}norm can be seen. Figure 3 shows the corresponding convergence rates. Again, also the L_{1}norm as well as a pointwise measured error can be seen.
parabolic PDE'sWe also treat parabolic equations
on the domain with boundary condition
for and
initioal condition for
for the elliptic operator
The coefficient function is chosen in a way so that
is the solution of our problem where
describes the initial value for

Bibliography 

Related projects 