2005 Reports

Tractability of quasilinear problems. II: Second-order elliptic problems

Werschulz, Arthur G.; Wozniakowski, Henryk

In a previous paper, we developed a general framework for establishing tractability and strong tractability for quasilinear multivariate problems in the worst case setting. One important example of such a problem is the solution of the Helmholtz equation −Δu + qu = f in the d-dimensional unit cube, in which u depends linearly on f , but nonlinearly on q. Here, both f and q are d-variate functions from a reproducing kernel Hilbert space with finite-order weights of order ω. This means that, although d can be arbitrary large, f and q can be decomposed as sums of functions of at most ω variables, with ω independent of d. In this paper, we apply our previous general results to the Helmholtz equation, subject to either Dirichlet or Neumann homogeneous boundary conditions. We study both the absolute and normalized error criteria. For all four possible combinations of boundary conditions and error criteria, we show that the problem is tractable. That is, the number of evaluations of f and q needed to obtain an ε- approximation is polynomial in ε −1 and d, with the degree of the polynomial depending linearly on ω. In addition, we want to know when the problem is strongly tractable, meaning that the dependence is polynomial only in ε −1 , independently of d. We show that if the sum of the weights defining the weighted reproducing kernel Hilbert space is uniformly bounded in d and the integral of the univariate kernel is positive, then the Helmholtz equation is strongly tractable for three of the four possible combinations of boundary conditions and error criterion, the only exception being the Dirichlet boundary condition under the normalized error criterion.