The long-term aim of the present work is to make significant progress in the numerical solution of large-scale transport problems: systems of partial differential equations of the advection-diffusion-reaction type, used in the modeling of pollution of the atmosphere, surface water and ground water. The three-dimensional nature of these models and the necessity of modeling transport and chemical exchange between different components over long time spans, requires very efficient algorithms. For advanced three-dimensional modeling, computer capacity (computing time and memory) still is a severe limiting factor. This limitation is felt in particular in the area of global air pollution modeling where the three-dimensional nature leads to huge numbers of grid points in each of which many calculations must be carried out. The application of sparse-grid techniques, which have already proven useful in multi-grid-accelerated solution methods, might offer a promising way-out. Of course, this should go without loss of accuracy and in combination with an appropriate, efficient time stepping process. Sparse grids were introduced by Zenger in the early nineties to reduce the degrees of freedom in finite element calculations. Recent literature in the field of reactive flow problems and multi-grid methods for stationary differential equations confines this very promising development.

Contrary to most multi-grid methods, the combination technique is an extrapolation technique rather than a defect-correction method. The final solution is a linear combination of solutions on semi-coarsened grids, where the coefficients of the combination are chosen such that there is a canceling in leading-order error terms. For a d-dimensional problem (d>1), the solution on a single grid of mesh width h requires ~ h^-d degrees of freedom to obtain an accuracy of O(h²), when using linear interpolation. In comparison, the combination technique could solve this problem using ~ h^-1(log h^-1)^d-1 degrees of freedom to obtain an accuracy of O(h² (log h^-1)^d-1). This clearly shows the potential of the combination technique. In fact, the complexity is only one-dimensional, except for a logarithmic factor, while the accuracy is only deteriorated by a logarithmic factor. Another appealing property of the combination technique is that it is inherently parallelizable, i.e., it constructs the final solution from ~ (log h^-1)^d-1 independent solutions which can be computed in parallel.

In the present work an analysis is given of the error that remains in the solution after applying the combination technique. Basically there are three sources of error: discretization errors, prolongation errors and an intrinsic representation error. The discretization errors are present in the semi-coarsened solutions due to spatial and temporal discretization. In the current work the temporal discretization errors are neglected. The prolongation errors are picked up when the semi-coarsened solutions are projected onto the fine grid. The representation error is always present in the combined solution, even if the semi-coarsened solutions are error-free. The representation error is of interest when the combination technique is used as a means of efficient function representation. When it is used to solve a differential equation, it is of less significance because then the combined discretization errors are dominant. Error analysis for function representation by the sparse-grid combination technique is a report on the representation error by the first two authors. The focus of the present work is on how the discretization errors that exist on the semi-coarsened grids propagate onto the fine grid where the final solution is constructed. In particular, it is shown how the discretization errors and prolongation errors interact. For example, it is shown that the order of the prolongation must match the order of the spatial discretization. The analysis leads to an explicit error expression for initial-value problems, providing insight into the structure of the error.

An interesting conclusion from the analysis is that for initial-value problems the error increases quadratically in time instead of linearly, as it does for a single-grid solution. The implication of this is that the time span over which the semi-coarse solutions are evolved should be limited. One way to limit the time span is to apply the combination technique repeatedly, each time doing a limited propagation in time, instead of a single propagation over a longer time interval.

Another key observation consists of how the discretization errors from the semi-coarsened grids manifest themselves on the fine grid. In particular, it is shown that error terms proportional to hx^p hy^p play a prominent role, i.e., they produce an error term proportional to h^p log h^-1 on the fine grid, for a two-dimensional problem. In fact, the leading-order error term on the fine grid comes forth from error terms proportional to hx² hy² on the semi-coarsened grids, for linear interpolation. This observation raises the question whether it is possible to eliminate the leading hx^p hy^p term from the expansion of the discretization error on the semi-coarsened grids by choosing a suitable spatial discretization. Some preliminary results on such discretizations will be presented.

Numerical experiments will be presented that confirm the analysis. Furthermore, results of a set of numerical tests (one of which is the Molenkamp test) are presented that illustrate the strong and weak points of the combination technique when applied to time-dependent problems. In particular, it will become apparent that grid-aligned problems are especially well suited to the combination technique. ------- End of Forwarded Message