Sparse grids provide an efficient representation of discrete solutions of partial differential equations with a competitive advantage especially for higher dimensional problems. They are mainly based on specific tensor products of one dimensional multi-resolution schemes and easily allow for adaptive grid refinement.
We present a key based addressing scheme for the nodes of the sparse grid. Along with a hash table storage this proves to be superior to conventional tree data structures. We propose a parallelization strategy for codes with adaptive grid refinement, which is based on space-filling curves. This results in a cheap, parallel partitioning and mapping algorithm, which can be executed whenever new workload is created due to local grid refinement.
Non-reflecting boundary conditions for problems of wave propagation are non-local in space and time. While the non-locality in space can be efficiently handled by Fourier or spherical expansions in special geometries, the arising temporal convolutions still form a computational bottleneck. In the present talk, a new algorithm for the evaluation of these convolution integrals is proposed. To compute a temporal convolution over Nt successive time steps, the algorithm requires O(Ntlog Nt) operations and O(log Nt) active memory. In the numerical examples, this algorithm is used to discretize the Dirichlet-to-Neumann and Neumann-to-Dirichlet operators arising from the formulation of non-reflecting boundary conditions in rectangular geometries for Schrödinger and wave equations.
Consider the classical problem of interpolating a rough (without point-values) function by continuous piecewise polynomials, but with the additional constraint of preserving positivity. We construct a positive interpolation operator into the space of piecewise linear finite elements with optimal approximation properties. We also give several intriguing impossibility results for such operators concerning boundary values at extreme points, invariance of finite element subspaces, and higher order accuracy. We finally apply positive interpolation to derive optimal a posteriori error estimators for elliptic variational inequalities both in the energy and maximum norms.
This work is joint with Z. Chen, K. Siebert, A. Vesser, and L. Wahlbin.
The numerical treatment of boundary integral equations by the boundary element method (BEM) leads to linear systems with large and dense system matrices. The assembling and application of these matrices is the most time consuming part in the process of the numerical solution of boundary integral equations. In the last years, various compression methods have been proposed to overcome the large costs of dealing with these matrices. In the talk we combine several of these methods and derive a multilevel-algorithm for the approximative evaluation of BEM matrices. We discuss its complexity and finally apply the algorithm to various boundary integral equations to show its numerical efficiency.
