The solution of multidimensional real Helmholtz equations on sparse grids

Sparse grids provide a very efficient method for the multilinear approximation of functions, especially in higher-dimensional spaces. In the d-dimensional space, the nodal multilinear basis on a grid with mesh size h = 2(-n) consists of O(2(nd)) basis functions and leads to an L_2-error of order O(4(-n)) and an H_1-error of order O(2(-n)). With sparse grids we get an L_2-error of order O(4(-n)n(d-1)) and an H_1-error of order O (2(-n)) with only O(2(n)n(d-1)) basis functions, if the function u fulfills the condition partial derivative(2d)/partial derivative x(1)(2) partial derivative x(2)(2)...partial derivative x(d)(2)u < infinity. Therefore, we can achieve much more accurate approximations with the same amount of storage. A data structure for the sparse grid representation of functions defined on cubes of arbitrary dimension and a finite element approach for the Helmholtz equation with sparse grid functions are introduced. Special emphasis is taken in the development of an efficient algorithm for the multiplication with the stiffness matrix. With an appropriate preconditioned conjugate gradient method leg-method), the linear systems can be solved efficiently. Numerical experiments are presented for Helmholtz equations and eigenvalue problems for the Laplacian in two and three dimensions, and for a six-dimensional Poisson problem. The results support the assertion that the L_2-error bounds for the sparse-grid approximation are also valid for sparse grid finite element solutions of elliptic differential equations. Problems with nonsmooth solutions are treated with adaptive sparse grids.