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. Woźniakowski
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?)

  • R. A. Adams and J. J. F. Fournier, Sobolev spaces, second ed., Pure and Applied Mathematics, vol. 140, Academic Press, Boston, 2003.
  • N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 51437, DOI
  • P. G. Ciarlet, Basic error estimates for elliptic problems, Handbook of numerical analysis, Vol. II, Handb. Numer. Anal., II, North-Holland, Amsterdam, 1991, pp. 17–351. MR 1115237
  • J. Dick, I. H. Sloan, X. Wang, and H. Woźniakowski, Good lattice rules in weighted Korobov spaces with general weights, To appear in Numerische Mathematik.
  • David Gilbarg and Neil S. Trudinger, Elliptic partial differential equations of second order, 2nd ed., Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 224, Springer-Verlag, Berlin, 1983. MR 737190
  • A. Messiah, Quantum mechanics, Dover, Mineola, NY, 1999.
  • Erich Novak and Henryk Woźniakowski, When are integration and discrepancy tractable?, Foundations of computational mathematics (Oxford, 1999) London Math. Soc. Lecture Note Ser., vol. 284, Cambridge Univ. Press, Cambridge, 2001, pp. 211–266. MR 1836619
  • J. T. Oden and J. N. Reddy, An introduction to the mathematical theory of finite elements, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1976. Pure and Applied Mathematics. MR 0461950
  • I. H. Sloan and H. Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1–33.
  • J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691
  • J. F. Traub and A. G. Werschulz, Complexity and information, Lezioni Lincee. [Lincei Lectures], Cambridge University Press, Cambridge, 1998. MR 1692462
  • G. W. Wasilkowski and H. Woźniakowski, Finite-order weights imply tractability of linear multivariate problems, J. Approx. Theory 130 (2004), no. 1, 57–77. MR 2086810, DOI
  • Arthur G. Werschulz, The computational complexity of differential and integral equations, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1991. An information-based approach; Oxford Science Publications. MR 1144521
  • A. G. Werschulz and H. Woźniakowski, Tractability of quasilinear problems. I: General results, Tech. Report CUCS-025-05, Columbia University, Department of Computer Science, New York, 2005, Submitted to J. Approx. Theory for publication. Available at
  • William P. Ziemer, Weakly differentiable functions, Graduate Texts in Mathematics, vol. 120, Springer-Verlag, New York, 1989. Sobolev spaces and functions of bounded variation. MR 1014685

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. Woźniakowski
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