Strong tractability of multivariate integration using quasi-Monte Carlo algorithms

Author:
Xiaoqun Wang

Journal:
Math. Comp. **72** (2003), 823-838

MSC (2000):
Primary 65C05, 65D30, 68Q25

DOI:
https://doi.org/10.1090/S0025-5718-02-01440-0

Published electronically:
June 25, 2002

MathSciNet review:
1954970

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study quasi-Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of depends on and the dimension . Strong tractability means that it does not depend on and is bounded by a polynomial in . The least possible value of the power of is called the *-exponent* of strong tractability. Sloan and Wozniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the -exponent of strong tractability is between 1 and 2. However, their proof is *not constructive*.

In this paper we prove *in a constructive way* that multivariate integration in some weighted Sobolev spaces is strongly tractable with -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Wozniakowski's assumption. We show that quasi-Monte Carlo algorithms using Niederreiter's -sequences and Sobol sequences achieve the optimal convergence order for any *independent of the dimension* with a worst case deterministic guarantee (where is the number of function evaluations). This implies that strong tractability with the best -exponent can be achieved in appropriate weighted Sobolev spaces by using Niederreiter's -sequences and Sobol sequences.

**1.**N. Aronszajn,*Theory of reproducing kernels*, Trans. Amer. Math. Soc.,**68**(1950), 337-404. MR**14:479c****2.**N. S. Bakhvalov,*On approximate computation of multiple integrals*, Vestnik Moskov. Univ. Ser. Mat. Mekh. Astr. Fiz. Khim**1959**, no. 4, 3-18 (Russian). MR**22:6077****3.**P. Bratley, B. L. Fox and H. Niederreiter,*Implementation and tests of low discrepancy sequences*, ACM Trans. Model. Comput. Simul.,**2**(1992), 195-213.**4.**R. E. Caflisch, W. Morokoff and A. Owen,*Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension*, J. Comp. Finance,**1**(1997), 27-46.**5.**H. Faure,*Discrépance de suites associées à un système de numération (en dimension s),*Acta Arith.,**41**(1982), 337-351. MR**84m:10050****6.**J. H. Halton,*On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals*, Numer. Math.,**2**(1960), 84-90. MR**22:12688****7.**F. J. Hickernell,*A generalized discrepancy and quadrature error bound*, Math. Comp.,**67**(1998), 299-322. MR**98c:65032****8.**F. J. Hickernell and X. Wang,*The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension*, Math. Comp.,**71**(2002), 1641-1661.**9.**F. J. Hickernell and H. Wozniakowski,*Integration and approximation in arbitrary dimension*, Advances in Comput. Math.,**12**(2000), 25-58. MR**2001d:65017****10.**R. Lidl and H. Niederreiter,*Introduction to Finite Fields and Their Applications*, Cambridge University Press, 1986. MR**88c:11073****11.**W. J. Morokoff and R. E. Caflisch,*Quasi-random sequences and their discrepancies*, SIAM J. Sci. Comput.,**15**(1994), 1251-1279. MR**95e:65009****12.**H. Niederreiter,*Low-discrepancy and low-dispersion sequences*, J. Number Theory,**30**(1988), 51-70. MR**89k:11064****13.**H. Niederreiter,*Random Number Generation and Quasi-Monte Carlo Methods*, SIAM, Philadelphia, 1992. MR**93h:65008****14.**H. Niederreiter and C. Xing,*Low-discrepancy sequences and global function fields with many rational places*, Finite Field Appl.,**2**(1996), 241-273. MR**97h:11080****15.**E. Novak and H. Wozniakowski,*Intractability results for integration and discrepancy*, J. Complexity,**17**(2001), 388-441.**16.**S. H. Paskov and J. F. Traub,*Faster valuation of financial derivatives*, J. Portfolio Management,**22**(1995), 113-120.**17.**I. H. Sloan and H. Wozniakowski,*When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?*J. Complexity,**14**(1998), 1-33. MR**99d:65384****18.**I. H. Sloan and H. Wozniakowski,*Tractability of multivariate integration for weighted Korobov classes*, J. Complexity,**17**(2001), 697-721.**19.**I. M. Sobol,*The distribution of points in a cube and the approximate evaluation of integrals*, Zh. Vychisl. Mat. i Mat. Fiz.,**7**(1967), 784-802. (Russian) MR**36:2321****20.**I. M. Sobol,*Multidimensional Quadrature Formulas and Haar Functions*, Izdat. Nauka, Moscow, 1969 (Russian). MR**54:10592****21.**J. F. Traub and A. G. Werschulz,*Complexity and Information*, Cambridge University Press, 1998. MR**2000m:65170****22.**G. W. Wasilkowski and H. Wozniakowski,*Weighted tensor product algorithms for linear multivariate problems*, J. Complexity,**15**(1999), 402-447. MR**2000h:65200****23.**H. Wozniakowski, Tractability and strong tractability of linear multivariate problems, J. Complexity,**10**(1994), 96-128. MR**95d:65117****24.**H. Wozniakowski,*Efficiency of quasi-Monte Carlo algorithms for high dimensional integrals*, in Monte Carlo and Quasi Monte Carlo Methods 1998 (H. Niederreiter and J. Spanier, eds.), Springer-Verlag, Berlin, 1999, 114-136.

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65C05,
65D30,
68Q25

Retrieve articles in all journals with MSC (2000): 65C05, 65D30, 68Q25

Additional Information

**Xiaoqun Wang**

Affiliation:
Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Email:
xwang@math.tsinghua.edu.cn

DOI:
https://doi.org/10.1090/S0025-5718-02-01440-0

Keywords:
Quasi--Monte Carlo methods,
low discrepancy sequences,
tractability,
strong tractability,
multidimensional integration

Received by editor(s):
March 7, 2001

Received by editor(s) in revised form:
August 16, 2001

Published electronically:
June 25, 2002

Additional Notes:
Supported by the NSF of China Grants 79970120 and 10001021.

Article copyright:
© Copyright 2002
American Mathematical Society