Finite-order weights imply tractability of multivariate integration
type: Item
instance of: scholarly article
title: Finite-order weights imply tractability of multivariate integration
zbMATH Open document ID: 1067.65006
author: Ian H. Sloan
author: Xiaoqun Wang
author: H. Woźniakowski
published in: Journal of Complexity
publication date: 2004-10-13T00:00:00Z
review text: The multivariate integration of high dimension \(s\) is discussed in the context of tractability and strong tractability of quasi-Monte Carlo algorithms. Although the number of input variables can be very large it is often observed in such problems that functions mainly depend on groups of just a few variables at a time. Such an example is computational finance, where the dimensions of hundreds or thousands are common. In this case the classical integration rules such as trapezoidal rule, Simpson's rule, Gaussian rule, etc., are not efficient, whereas Monte Carlo (MC) and quasi-Monte Carlo (QMC) algorithms are more succesful. These algorithms take the average of function values over either random (MC) or deterministic (QMC) set of points \(P_n:=\{ {\mathbf x}_0, {\mathbf x}_1, \ldots , {\mathbf x}_{n-1} \}\). The basic question is how the minimal number of function values \(n\) needed to reduce the initial error by a factor \(\varepsilon\) depends on \(s\) and \(\varepsilon^{-1}\). The strong tractability implies no dependence on \(s\) and only polynomial dependence on \(\varepsilon^{-1}\), whereas polynomial dependence on both \(s\) and \(\varepsilon^{-1}\) implies tractability. Tractability usually does not hold in Hilbert spaces such as classical Sobolev and Korobov spaces where all variables play the same role. To obtain tractability, weighted Sobolev and Korobov spaces are considered. Besides, the considered ones are reproducing kernel Hilbert spaces. The existence of efficient QMC algorithms for anchored and unanchored Sobolev kernels is considered. In the case of anchored Sobolev space, the strong tractability is proven for arbitrary finite order weights. In the case of unanchored Sobolev space the tractability is shown for all bounded finite order weights. In both cases the dependence on \(\varepsilon^{-1}\) is quadratic. For finite order weights, almost linear dependence on \(\varepsilon^{-1}\) can be achieved at the expese of polynomial dependence on \(s\)…
Mathematics Subject Classification ID: 65C05
zbMATH DE Number: 2107423
zbMATH Keywords: Lattice rules
zbMATH Keywords: multivariate integration
zbMATH Keywords: tractability
zbMATH Keywords: low discrepancy sequences
zbMATH Keywords: quasi-Monte Carlo algorithms
zbMATH Keywords: weighted Sobolev and Korobov spaces
zbMATH Keywords: reproducing kernel Hilbert spaces
zbMATH Keywords: worst-case error bounds
reviewed by: J. Kaupužs
MaRDI profile type: Publication
full work available at URL: j.jco.2003.11.003
OpenAlex ID: W2043466875
cites work: Good lattice rules in weighted Korobov spaces with general weights
cites work: Liberating the weights
cites work: On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals
cites work: A generalized discrepancy and quadrature error bound
cites work: On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}
cites work: The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
cites work: Integration and approximation in arbitrary dimensions
cites work: Q4003879
cites work: When are integration and discrepancy tractable?
cites work: Intractability results for integration and discrepancy
cites work: Q4889887
cites work: On the step-by-step construction of quasi--Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces
cites work: Constructing Randomly Shifted Lattice Rules in Weighted Sobolev Spaces
cites work: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
cites work: Tractability of multivariate integration for weighted Korobov classes
cites work: Tractability of integration in non-periodic and periodic weighted tensor product Hilbert spaces
cites work: On the distribution of points in a cube and the approximate evaluation of integrals
cites work: Q4226567
cites work: Strong tractability of multivariate integration using quasi–Monte Carlo algorithms
cites work: The effective dimension and quasi-Monte Carlo integration
cites work: Why Are High-Dimensional Finance Problems Often of Low Effective Dimension?
cites work: Weighted tensor product algorithms for linear multivariate problems
DOI: 10.1016/J.JCO.2003.11.003
description: scientific article; zbMATH DE number 2107423