When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?

DOI10.1006/jcom.1997.0463zbMath1032.65011MaRDI QIDQ1265135

Ian H. Sloan, Henryk Woźniakowski

Publication date: 3 December 2003

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/054a203422d121cd4464d953846f53576a41c573

zbMATH Keywords

multivariate integration; quasi-Monte Carlo algorithms; worst case error bounds

Mathematics Subject Classification ID

65C05: Monte Carlo methods

65Y20: Complexity and performance of numerical algorithms

11K45: Pseudo-random numbers; Monte Carlo methods

Related Items

Weighted discrepancy of Faure-Niederreiter nets for a certain sequence of weights, Fast convergence of quasi-Monte Carlo for a class of isotropic integrals, Worst-case errors in a Sobolev space setting for cubature over the sphere S², Strong tractability of multivariate integration using quasi–Monte Carlo algorithms, On tractability of weighted integration over bounded and unbounded regions in ℝ^{𝕤}, On strong tractability of weighted multivariate integration, Reducing the construction cost of the component-by-component construction of good lattice rules, Strong tractability of integration using scrambled Niederreiter points, Construction algorithms for polynomial lattice rules for multivariate integration, Statistical properties of generalized discrepancies, On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation, A Taylor space for multivariate integration, Intractability results for integration and discrepancy, What is the complexity of surface integration?, Uniform distribution, discrepancy, and reproducing kernel Hilbert spaces, Constructions of general polynomial lattices for multivariate integration, Tractability of integration in non-periodic and periodic weighted tensor product Hilbert spaces, On the mean square weighted \(\mathcal {L}_2\) discrepancy of randomized digital nets in prime base, Randomly shifted lattice rules for unbounded integrands, Exact cubature for a class of functions of maximum effective dimension, The tent transformation can improve the convergence rate of quasi-Monte Carlo algorithms using digital nets, A component-by-component approach to efficient numerical integration over products of spheres, The construction of good extensible Korobov rules, On the convergence rate of the component-by-component construction of good lattice rules, Tractability of quasilinear problems. I: General results, Generalized tractability for multivariate problems. I: Linear tensor product problems and linear information, Estimation and detection of high-variable functions from Sloan-Woźniakowski space, Koksma-Hlawka type inequalities of fractional order, Quasi-Monte Carlo for highly structured generalised response models, Efficient deterministic numerical simulation of stochastic asset-liability management models in life insurance, New averaging technique for approximating weighted integrals, Scrambling Sobol' and Niederreiter-Xing points, Quasi-regression, The price of pessimism for multidimensional quadrature, Tractability of multivariate integration for periodic functions, Tractability of multivariate integration for weighted Korobov classes, Quasi-random simulation of linear kinetic equations, The exact exponent of sparse grid quadratures in the weighted case, Integration and approximation based on scramble sampling in arbitrary dimensions, Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, Sufficient conditions for fast quasi-Monte Carlo convergence, My dream quadrature rule, Open problems for tractability of multivariate integration., On stochastic formalisms in transition state theory, Randomized Halton sequences, The Brownian bridge does not offer a consistent advantage in quasi-Monte Carlo integration, A new measure of irregularity of distribution and quasi-Monte Carlo methods for global optimization, Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces, Quasi-Monte Carlo methods can be efficient for integration over products of spheres, Computational complexity of the integration problem for anisotropic classes, Assessing linearity in high dimensions., The effective dimension and quasi-Monte Carlo integration, A constructive approach to strong tractability using quasi-Monte Carlo algorithms, Finite-order weights imply tractability of linear multivariate problems, Finite-order weights imply tractability of multivariate integration, \(I\)-binomial scrambling of digital nets and sequences, Liberating the weights, On polynomial-time property for a class of randomized quadratures, On the root mean square weighted \(L_{2}\) discrepancy of scrambled nets, Intractability results for positive quadrature formulas and extremal problems for trigonometric polynomials, Weighted tensor product algorithms for linear multivariate problems, Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules, On the existence of higher order polynomial lattices based on a generalized figure of merit, Constructions of general polynomial lattice rules based on the weighted star discrepancy, Periodization strategy may fail in high dimensions, Low discrepancy sequences in high dimensions: how well are their projections distributed?, New Brownian bridge construction in quasi-Monte Carlo methods for computational finance, Tractability properties of the weighted star discrepancy, Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points, Randomly shifted lattice rules on the unit cube for unbounded integrands in high dimensions, Good lattice rules in weighted Korobov spaces with general weights, The weighted \(b\)-adic diaphony, Dyadic diaphony of digital nets over \(\mathbb Z_2\), Diaphony, discrepancy, spectral test and worst-case error, On the necessity of low-effective dimension, Non-linear approximation of functions with mixed smoothness by sets of finite pseudo-dimension, The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension, Tractability of quasilinear problems II: Second-order elliptic problems, Good lattice rules based on the general weighted star discrepancy, The construction of extensible polynomial lattice rules with small weighted star discrepancy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sequences, discrepancies and applications
• Tractability and strong tractability of linear multivariate problems
• Explicit cost bounds of algorithms for multivariate tensor product problems
• Tractability of tensor product linear operators
• Quasi-Monte Carlo integration
• Multidimensional quadrature algorithms at higher degree and/or dimension
• Smoothness and dimension reduction in quasi-Monte Carlo methods
• Computing discrepancies of Smolyak quadrature rules
• A Note on the Generation of Random Normal Deviates
• On irregularities of distribution, IV
• Quasi-Monte Carlo Methods in Numerical Finance
• A generalized discrepancy and quadrature error bound
• Toward real-time pricing of complex financial derivatives
• On tractability of path integration
• Some applications of multidimensional integration by parts
• Theory of Reproducing Kernels
• On irregularities of distribution