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

DOI:
https://doi.org/10.1090/S0025-5718-06-01927-2

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 in the -dimensional unit cube, in which depends linearly on , but nonlinearly on . Here, both and are -variate functions from a reproducing kernel Hilbert space with finite-order weights of order . This means that, although can be arbitrarily large, and can be decomposed as sums of functions of at most variables, with independent of .

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 and needed to obtain an -approximation is polynomial in and , with the degree of the polynomial depending linearly on . In addition, we want to know when the problem is *strongly tractable*, meaning that the dependence is polynomial only in , independently of . We show that if the sum of the weights defining the weighted reproducing kernel Hilbert space is uniformly bounded in 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.

**1.**R. A. Adams and J. J. F. Fournier,*Sobolev spaces*, second ed., Pure and Applied Mathematics, vol. 140, Academic Press, Boston, 2003.**2.**N. Aronszajn,*Theory of reproducing kernels*, Trans. Amer. Math. Soc.**68**(1950), 337–404. MR**51437**, https://doi.org/10.1090/S0002-9947-1950-0051437-7**3.**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****4.**J. Dick, I. H. Sloan, X. Wang, and H. Wozniakowski,*Good lattice rules in weighted Korobov spaces with general weights*, To appear in*Numerische Mathematik*.**5.**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****6.**A. Messiah,*Quantum mechanics*, Dover, Mineola, NY, 1999.**7.**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****8.**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****9.**I. H. Sloan and H. Wozniakowski,*When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?*, J. Complexity**14**(1998), no. 1, 1-33.**10.**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****11.**J. F. Traub and A. G. Werschulz,*Complexity and information*, Lezioni Lincee. [Lincei Lectures], Cambridge University Press, Cambridge, 1998. MR**1692462****12.**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**, https://doi.org/10.1016/j.jat.2004.06.011**13.**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****14.**A. G. Werschulz and H. Wozniakowski,*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`http://mice.cs.columbia.edu/getTechreport.php?techreportID=248&format=pdf&`.**15.**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**

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

Email:
agw@cs.columbia.edu

**H. Wozniakowski**

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

Email:
henryk@cs.columbia.edu

DOI:
https://doi.org/10.1090/S0025-5718-06-01927-2

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