Digital inversive vectors can achieve polynomial tractability for the weighted star discrepancy and for multivariate integration

DOI10.1090/PROC/13490MaRDI QIDQ5270132zbMATH OpenOpenAlexFDO

Authors Josef Dick, Domingo Gómez-Pérez, Arne Winterhof, Friedrich Pillichshammer

Publication date 22 June 2017

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.06521

zbMATH Keywords

pseudorandom numbersquasi-Monte Carlotractabilityweighted star discrepancy

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Pseudo-random numbers; Monte Carlo methods (11K45) Exponential sums (11T23) Monte Carlo methods (65C05) Random number generation in numerical analysis (65C10)

Abstract: We study high-dimensional numerical integration in the worst-case setting. The subject of tractability is concerned with the dependence of the worst-case integration error on the dimension. Roughly speaking, an integration problem is tractable if the worst-case error does not explode exponentially with the dimension. Many classical problems are known to be intractable. However, sometimes tractability can be shown. Often such proofs are based on randomly selected integration nodes. Of course, in applications true random numbers are not available and hence one mimics them with pseudorandom number generators. This motivates us to propose the use of pseudorandom vectors as underlying integration nodes in order to achieve tractability. In particular, we consider digital inverse vectors and present two examples of problems, the weighted star discrepancy and integration of H"older continuous, absolute convergent Fourier- and cosine series, where the proposed method is successful.

Recommendations

• When are integration and discrepancy tractable?
• Strong tractability of multivariate integration using quasi–Monte Carlo algorithms
• On strong tractability of weighted multivariate integration
• Intractability results for integration and discrepancy
• Discrepancy, integration and tractability

Cites work

• A fast algorithm for computing multiplicative inverses in \(\text{GF}(2^ m)\) using normal bases
• Covering numbers, dyadic chaining and discrepancy
• Exponential Sums and Goppa Codes: I
• Finite binary sequences constructed by explicit inversive methods
• High-dimensional integration: The quasi-Monte Carlo way
• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 607286 (Why is no real title available?)
• scientific article; zbMATH DE number 204179 (Why is no real title available?)
• scientific article; zbMATH DE number 3367521 (Why is no real title available?)
• Incomplete exponential sums over finite fields and their applications to new inversive pseudorandom number generators
• Introduction to quasi-Monte Carlo integration and applications
• Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series
• On the distribution of some new explicit inverse pseudorandom numbers and vectors
• On the linear complexity profile of some new explicit inversive pseudorandom numbers
• Probabilistic discrepancy bound for Monte Carlo point sets
• The curse of dimensionality for numerical integration of smooth functions
• The curse of dimensionality for numerical integration of smooth functions. II
• The curse of dimensionality for the class of monotone functions and for the class of convex functions
• The inverse of the star-discrepancy depends linearly on the dimension
• The inverse of the star-discrepancy problem and the generation of pseudo-random numbers
• The weighted star discrepancy of Korobov’s p-sets
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Tractability of multivariate problems. Volume III: Standard information for operators
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?

Cited in

(7)

• Tractability properties of the weighted star discrepancy of regular grids
• A note on \((s,t)\)-weak tractability of the weighted star discrepancy of regular grids
• Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
• On the information complexity for integration in subspaces of the Wiener algebra
• Tractability results for integration in subspaces of the Wiener algebra
• Conditions for tractability of the weighted L_p-discrepancy and integration in non-homogeneous tensor product spaces
• Probabilistic weighted star discrepancy bound based on the general equal measure partition

This page was built for publication: Digital inversive vectors can achieve polynomial tractability for the weighted star discrepancy and for multivariate integration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5270132)