Numerical Analysis Group Research Report NA-07/04

February 2007, 52 pages, .pdf file

Partial differential equations with nonnegative characteristic form arise in numerous mathematical models in science. In problems of this kind, the exponential growth of computational complexity as a function of the dimension d of the problem domain, the so-called ``curse of dimension'', is exacerbated by the fact that the problem may be transport-dominated. We develop the numerical analysis of stabilized sparse tensor-product finite element methods for such high-dimensional, non-self-adjoint and possibly degenerate second-order partial differential equations, using piecewise polynomials of degree p > 0. Our convergence analysis is based on new high-dimensional approximation results in sparse tensor-product spaces. By tracking the dependence of the various constants on the dimension $d$ and the polynomial degree p, we show in the case of elliptic transport-dominated diffusion problems that for p > 0 the error constant exhibits exponential decay as d tends to infinity. In the general case when the characteristic form of the partial differential equation is non-negative, under a mild condition relating p to d, the error constant is shown to grow no faster than quadratically in d. In any case, the sparse stabilized finite element method exhibits an optimal rate of convergence with respect to the mesh-size, up to a factor that is polylogarithmic in the mesh-size.

Dedicated to Henryk Wozniakowski, on the occasion of his 60th birthday.