The author presents details of implementation of sparse grid methods for boundary value problems for partial differential equations. Hierarchical basis functions have recently been introduced into the context of partial differential equations by R. E. Bank, T. F. Dupont, and H. Yserentant [Numer. Math. 52, No. 4, 427-458 (1988; Zbl 0645.65074)], although they were common in the context of numerical quadrature before that. In the present paper, the author considers efficient methods for their implementation on sparse tensor product grids.
Sparse grids and hierarchical basis functions promise a significant improvement in computational efficiency because they achieve a reduction from \(O(N^d)\) to \(O(N\log^{d-1}N)\) degrees of freedom in \(d\)-dimensional regions with smallest mesh widths of \(1/N\). This reduction is achieved with only a modest reduction in accuracy. The key to realizing improved computational efficiency is in implementation.
The author presents a recursive approach based on a binary tree data structure. The methods for generating higher-order basis functions, constructing stiffness matrices, transferring information from finer to coarser grids in multigrid algorithms, and performing the fundamental matrix-vector multiplication necessary for iterative solution of systems of equations are each described in a one-dimensional setting. Extension from one to multiple dimensions is accomplished by recursion.
Two finite element approaches are presented. One uses sparse grids for both shape and test functions, the other uses sparse grids for shape functions and full tensor product grids for test functions. The latter method trades difficulty in transferring information across levels in a multigrid scheme for difficulty in solving the resulting nonsymmetric matrix equations. On balance, the nonsymmetric method appears to be advantageous.
A numerical example solving a Dirichlet problem for the two-dimensional Laplace equation is presented. The example illustrates excellent the accuracy improvement for increasing the order of approximation and the relatively slow growth in the condition number of the matrix equations. Running times are not reported.