THE SOLUTION OF MULTIDIMENSIONAL REAL HELMHOLTZ EQUATIONS ON SPARSE GRIDS

Sparse grids provide a very efficient method for the multilinear appro ximation 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 spa rse 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 fu nction u fulfills the condition partial derivative(2d)/partial derivat ive 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 a nd a finite element approach for the Helmholtz equation with sparse gr id functions are introduced. Special emphasis is taken in the developm ent of an efficient algorithm for the multiplication with the stiffnes s 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 probl ems for the Laplacian in two and three dimensions, and for a six-dimen sional Poisson problem. The results support the assertion that the L_2 -error bounds for the sparse-grid approximation are also valid for spa rse grid finite element solutions of elliptic differential equations. Problems with nonsmooth solutions are treated with adaptive sparse gri ds.