Tractability of the Helmholtz equation with non-homogeneous Neumann boundary conditions: Relation to L2-approximation

Werschulz, Arthur G.

We want to compute a worst case ε-approximation to the solution of the Helmholtz equation −∆u+qu = f over the unit d-cube Id, subject to Neumann boundary conditions ∂νu = g on ∂Id. Let card(ε,d) denote the minimal number of evaluations of f, g, and q needed to compute an absolute or normalized ε- approximation, assuming that f , g, and q vary over balls of weighted reproducing kernel Hilbert spaces. This problem is said to be weakly tractable if card(ε, d) grows sub exponentially in ε−1 and d. It is said to be polynomially tractable if card(ε, d) is polynomial in ε−1 and d, and strongly polynomially tractable if this polynomial is independent of d. We have previously studied tractability for the homogeneous version g = 0 of this problem. In this paper, we investigate the tractability of the non-homogeneous problem, with general g. 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 weight sum is sub linearly 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 weight sum 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 d-variate function can be decomposed as 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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-043-07
Published Here
April 27, 2011