Academic Commons

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.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-016-94
Published Here
February 3, 2012