Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Tractability of quasilinear problems II: Second-order elliptic problems

Authors: A. G. Werschulz and H. Wozniakowski
Journal: Math. Comp. 76 (2007), 745-776
MSC (2000): Primary 65N15; Secondary 41A65
Published electronically: November 30, 2006
MathSciNet review: 2291835
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In a previous paper, we developed a general framework for establishing tractability and strong tractability for quasilinear multivariate problems in the worst case setting. One important example of such a problem is the solution of the Helmholtz equation $ -\Delta u + qu = f$ in the $ d$-dimensional unit cube, in which $ u$ depends linearly on $ f$, but nonlinearly on $ q$. Here, both $ f$ and $ q$ are $ d$-variate functions from a reproducing kernel Hilbert space with finite-order weights of order $ \omega$. This means that, although $ d$ can be arbitrarily large, $ f$ and $ q$ can be decomposed as sums of functions of at most $ \omega$ variables, with $ \omega$ independent of $ d$.

In this paper, we apply our previous general results to the Helmholtz equation, subject to either Dirichlet or Neumann homogeneous boundary conditions. We study both the absolute and normalized error criteria. For all four possible combinations of boundary conditions and error criteria, we show that the problem is tractable. That is, the number of evaluations of $ f$ and $ q$ needed to obtain an $ \varepsilon $-approximation is polynomial in  $ \varepsilon ^{-1}$ and $ d$, with the degree of the polynomial depending linearly on $ \omega$. In addition, we want to know when the problem is strongly tractable, meaning that the dependence is polynomial only in  $ \varepsilon ^{-1}$, independently of $ d$. We show that if the sum of the weights defining the weighted reproducing kernel Hilbert space is uniformly bounded in $ d$ and the integral of the univariate kernel is positive, then the Helmholtz equation is strongly tractable for three of the four possible combinations of boundary conditions and error criteria, the only exception being the Dirichlet boundary condition under the normalized error criterion.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65N15, 41A65

Retrieve articles in all journals with MSC (2000): 65N15, 41A65

Additional Information

A. G. Werschulz
Affiliation: Department of Computer and Information Sciences, Fordham University, New York, New York 10023 and Department of Computer Science, Columbia University, New York, New York 10027

H. Wozniakowski
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027 and Institute of Applied Mathematics, University of Warsaw, Poland

Keywords: Complexity, tractability, high-dimensional problems, elliptic partial differential equations, reproducing kernel hilbert spaces, quasi-linear problems, finite-order weights
Received by editor(s): November 8, 2005
Received by editor(s) in revised form: January 17, 2006
Published electronically: November 30, 2006
Additional Notes: This research was supported in part by the National Science Foundation
Article copyright: © Copyright 2006 American Mathematical Society