Academic Commons


Complexity of Indefinite Elliptic Problems

Werschulz, Arthur G.

We study the complexity of 2mth order definite elliptic problems Lu = f (with homogeneous Dirichlet boundary conditions) over a d-dimensional do- main Ω, error being measured in the Hm(Ω)-norm. The problem elements f belong to the unit ball of Wr,p(Ω), where p ∈ [2,∞] andr > d/p. Informa- tion consists of (possibly-adaptive) noisy evaluations of f or the coefficients of L. The absolute error in each noisy evaluation is at most δ. We find that the nth minimal radius for this problem is proportional to n−r/d + δ,and that a noisy finite element method with quadrature (FEMQ), which uses only function values, and not derivatives, is a minimal error algorithm. This noisy FEMQ can be efficiently implemented using multigrid techniques. Using these results, we find tight bounds onthe ε-complexity (minimal cost of calculating anε-approximation) for this problem, said bounds depending on the cost c(δ) of calculating a δ-noisy information value. As an example, if the cost of a δ- noisy evaluation isc(δ) = δ−s (for s > 0), then the complexity is proportional to (1/ε)d/r+s.


More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-084-83
Published Here
October 26, 2011
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.