1994 Reports

The Complexity of Multivariate Elliptic Problems with Analytic Data

Werschulz, Arthur G.

Let F be a class of functions defined on a d-dimensional domain. Our task is to compute H m -norm ϵ-approximations to solutions of 2mth-order elliptic boundary-value problems Lu = f for a fixed L and for f ∈ F. We assume that the only information we can compute about f ∈ F is the value of a finite number of continuous linear functions of f, each evaluation having cost c(d). Previous work has assumed that F was the unit ball of a Sobolev space Hr of fixed smoothness r, and it was found that the complexity of computing an ϵ-approximation was comp(ϵ; d) = Θ(c(d)(1/ϵ) d=(r+m) ). Since the exponent of 1=ϵ depends on d, we see that the problem is intractable in 1=ϵ for any such F of fixed smoothness r. In this paper, we ask whether we can break intractability by letting F be the unit ball of a space of infinite smoothness. To be specific, we let F be the unit ball of a Hardy space of analytic functions defined over a complex d-dimensional ball of radius greater than one. We then show that the problem is tractable in 1/ϵ. More precisely, we prove that comp (ϵ; d) = Θ(c (d) (ln1/ϵ) d), where Θ-constant depends on d. Since for any p > 0, there is a function K(.) such that comp(ϵ, d) ≤ c(d)K(d)(1/ϵ)p for sufficiently small ϵ, we see that the problem is tractable, with (minimal) exponent 0. Furthermore, we show how to construct a finite element p-method (in the sense of Babuska) that can compute an ϵ-approximation with cost Θ(c(d)(ln1/ϵ) d). Hence this finite element method is nearly optimal complexity algorithm for d-dimensional elliptic problems with analytic data.