Adaptive sparse grid multilevel methods for elliptic PDEs based on finite differences (Q1271537)

An adaptive multilevel approach for solving elliptic partial differential equations (PDEs) is presented. The method is based on a multiscale basis which is constructed using tensor products of one-dimensional hierarchical basis functions. At first, the corresponding subspace splitting representation of a function is given. Finite-dimensional approximations to a function are obtained by truncating the infinite series associated to the multiscale representation. This is characterized by a finite set of active levels and index number pairs with associated hierarchical coefficients. The realization of operations, as e.g. addition, subtraction, and multiplication, working with such truncated functions is discussed. Furthermore, discrete differential operators for first and second derivatives which are based on finite differences are introduced. The consistency order of the constructed hierarchical difference operators is given. These operations and operators are used to discretize elliptic partial differential equations. The resulting systems of algebraic equations are solved by means of the preconditioned BiCG method. Different numerical examples with non-adapted sparse grids as well as adaptively refined grids are presented. For the implementation of the methods hash tables as data structure are used. This new idea to use the hash table approach for adaptive multilevel methods for partial differential equations is explained in detail.