Tractability of the Helmholtz equation with non-homogeneous Neumann boundary conditions: The relation to the L2L2-approximation

We want to compute a worst case εε-approximation to the solution of the Helmholtz equation −Δu+qu=f over the unit dd-cube IdId, subject to Neumann boundary conditions ∂νu=g on ∂Id∂Id. We measure error in the H1(Id)H1(Id)-norm. Let card(ε,d)card(ε,d) denote the minimal number of evaluations of ff, gg, and qq needed to compute an absolute or normalized εε-approximation, assuming that ff, gg, and qq vary over balls of weighted reproducing kernel Hilbert spaces. This problem is said to be weakly tractable if card(ε,d)card(ε,d) grows subexponentially in ε−1ε−1 and dd. It is said to be polynomially tractable if card(ε,d)card(ε,d) is polynomial in ε−1ε−1 and dd, and strongly polynomially tractable if this polynomial is independent of dd. We have previously studied tractability for the homogeneous version g=0g=0 of this problem. In this paper, we investigate the tractability of the non-homogeneous problem, with general gg. Using new perturbation estimates having explicit constants, we are able to relate the tractability of this problem to that of the L2(Id)L2(Id)-approximation problem. First, suppose that we use product weights, in which the role of any variable is moderated by its particular weight. We then find that if the sum of the weights is sublinearly bounded, then the problem is weakly tractable; moreover, this condition is more or less necessary. We then show that the problem is polynomially tractable if the sum of the weights is logarithmically or uniformly bounded, and we estimate the exponents of tractability for these two cases. Next, we turn to finite-order weights of fixed order ωω, in which a dd-variate function can be decomposed as a sum, each term depending on at most ωω variables. We show that the problem is always polynomially tractable for finite-order weights, and we give estimates for the exponents of tractability. Since our results so far have established nothing stronger than polynomial tractability, we look more closely at whether strong polynomial tractability is possible. We show that our problem is never strongly polynomially tractable for the absolute error criterion. Moreover, we believe that the same is true for the normalized error criterion, but we have been able to prove this lack of strong tractability only when certain conditions hold on the weights. Finally, we use the Korobov and min kernels, along with product weights, to illustrate our results.