Collection of abstracts 14th GAMM-Seminar Kiel on Concepts of Numerical Software January 23rd to 25th, 1998.

Friday, January 23rd, 1998

Software concepts of a sparse grid finite difference code

Sparse grids provide an efficient representation of discrete solutions of PDEs and are mainly based on specific tensor products of 1D hierarchical basis ansatz functions. They easily allow adaptive refinement and compression. We present special finite difference operators on sparse grids that possess nearly the same properties than full grid operators do. Especially for the higher dimensional case this approach gives an important advantage over the convential $h$-version of the finite element method which results in an $\Co (\varepsilon^{-\frac{d}{2}})$ work count (diffusion and convection terms with central differences) and an $\Co (\varepsilon^{-d})$ work count (convection terms in the upwind case), respectively.

Using this approach, partial differential equations of second order can be discretized straightforwardly. Furthermore, the hierarchical sparse grid approach allows for simple and efficient error indicators for adaptive refinement.

We present hash tables as a new data structure for sparse grids. Here, direct access on the nodes is provided which is important for hierarchical transformations as well as for finite difference operators. This way expensive traditional tree data structures are avoided, which can be annoying especially in parallel implementations, where we use space-filling curves as hash table addresses.

We report on an adaptive, parallel, finite difference multigrid code for the solution of partial differential equations. The code is based on two software concepts: We use space-filling curves for the addressing of vertices and geometric entities. Space-filling curve based enumeration schemes lead to a cheap and efficient way of parallel data partitioning.

Many parts of the numerics is performed in linear, contiguous Fortran style vectors. The concepts of geometry, grids, vectors, solution fields, numerical linear algebra, nonlinear solvers and problem dependent differential operators are well separated through different class hierarchies.

The above techniques are now employed within a procedure for the solution of the Navier Stokes equations in 3D. Here we discretize by a projection method and obtain Poisson problems and convection-diffusion problems. These are treated by our adaptive sparse grid finite difference method.