language: en

The complexity of multivariate elliptic problems with analytic data

Technical Report CUCS-016-94
Arthur G. Werschulz
Division of Science and Mathematics, Fordham University
College at Lincoln Center New York, NY 10023
and Department of Computer Science Columbia University
New York, NY 10023
June 28, 1994

Abstract. 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 2 F . We assume that the only information we can compute about f 2 F is the value of a finite number of continuous linear functionals of f, each evaluation having cost c(d). Previous work has assumed that F was the unit ball of a Sobolev space H r of fixed smoothness r, and it was found that the complexity of computing an "-approximation was comp("; d) = fi(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) = fi(c(d)(ln 1=") d ), where the fi-constant depends on d. Since for any p &gt; 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 fi(c(d)(ln 1=") d ). Hence this finite element method is a nearly optimal complexity algorithm for d-dimensional elliptic problems with analytic data.

1. Introduction