×

Digital nets and sequences constructed over finite rings and their application to quasi-Monte Carlo integration. (English) Zbl 0876.11042

The concept of a \((t,m,s)\) net (for this notion see the excellent monograph [H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM (1992; Zbl 0761.65002)]) and of \((t,s)\)-sequences is of fundamental importance for high-dimensional quasi-Monte Carlo integration, in theory as well as in practice. It allows for the construction of so-called “low discrepancy” point sets, which serve as the nodes at which the integrand is computed. Until now, all construction methods for \((t,m,s)\) nets of practical relevance are digital methods over certain rings \(R\). That means that digit expansions in some integer base \(b\geq 2\) are used to define the net.
In this paper, the authors present a much more general version of this approach to numerical integration based on digital nets over arbitrary finite rings. They provide an error bound for integrands with rapidly converging Walsh series. Further important results of this paper concern the existence of digital nets and of digital sequences constructed over arbitrary rings. In particular, necessary and sufficient conditions for the existence of digital \((0,m,s)\)-nets and of digital \((0,s)\)-sequences are exhibited. In the final section, the authors give explicit constructions of digital \((t,m,s)\)-nets and digital \((t,s)\)-sequences in the case \(R=\mathbb{Z}_b\).

MSC:

11K38 Irregularities of distribution, discrepancy
65D30 Numerical integration
11K45 Pseudo-random numbers; Monte Carlo methods
42C10 Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.)

Citations:

Zbl 0761.65002
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Chrestenson, H. E.: A class of generalized Walsh functions. Pacific J. Math.5, 17-31 (1955). · Zbl 0065.05302
[2] Faure, H.: Discr?pance de suites associ?es ? un syst?me de num?ration (en dimensions). Acta Arith.41, 337-351 (1982). · Zbl 0442.10035
[3] Hansen, T., Mullen, G. L., Niederreiter, H.: Good parameters for a class of node sets in quasi-Monte Carlo integration. Math. Comp.61, 225-234 (1993). · Zbl 0792.11025
[4] Lang, S.: Algebra. Reading, Mass.: Addison-Wesley. 1965.
[5] Larcher, G.: Nets obtained from rational functions over finite fields. Acta Arith.63, 1-13 (1993). · Zbl 0770.11040
[6] Larcher, G.: On the distribution of an analog to classical Kronecker-sequences. J. Number Theory,52, 198-215 (1995). · Zbl 0824.11045
[7] Larcher, G., Lau?, A., Niederreiter, H., Schmid, W. Ch.: Optimal polynomials for (t, m, s)-nets and numerical integration of multivariate Walsh series. To appear in: SIAM J. Numer. Analysis, 1997. · Zbl 0861.65019
[8] Larcher, G., Niederreiter, H.: Generalized (t, s)-sequences, Kronecker-type sequences, and diophantine approximations of formal Laurent series. Trans. Amer. Math. Soc.347, 2051-2073 (1995). · Zbl 0829.11039
[9] Larcher, G., Schmid, W. Ch., Wolf, R.: Representation of functions as Walsh series to different bases and an application to the numerical integration of high-dimensional Walsh series. Math. Comp.63, 701-716 (1994). · Zbl 0821.42017
[10] Larcher, G., Schmid, W. Ch., Wolf, R.: Quasi-Monte Carlo methods for the numerical integration of multivariate Walsh series. To appear in: Math. Comp. Modelling, 1995. · Zbl 0831.65018
[11] Larcher, G., Traunfellner, C.: On the numerical integration of Walsh series by number-theoretic methods. Math. Comp.63, 277-291 (1994). · Zbl 0806.65013
[12] Mullen, G. L., Whittle, G.: Point sets with uniformity properties and orthogonal hypercubes. Mh. Math.113, 265-273 (1992). · Zbl 0765.11032
[13] Niederreiter, H.: Point sets and sequences with small discrepancy. Mh. Math.104, 273-337 (1987). · Zbl 0626.10045
[14] Niederreiter, H.: Low-discrepancy and low-dispersion sequences. J. Number Theory30, 51-70 (1988). · Zbl 0651.10034
[15] Niederreiter, H.: Low-discrepancy point sets obtained by digital constructions over finite fields. Czechoslovak Math. J.42, 143-166 (1992). · Zbl 0757.11024
[16] Niederreiter, H.: Orthogonal arrays and other combinatorial aspects in the theory of uniform point distributions in unit cubes. Discrete Math.106/107, 361-367 (1992). · Zbl 0918.11045
[17] Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. Philadelphia: SIAM. 1992. · Zbl 0761.65002
[18] Onneweer, C. W., Waterman, D.: Uniform convergence of Fourier series on groups, I. Michigan Math. J.18, 265-273 (1971). · Zbl 0225.43013
[19] Rudin, W.: Fourier Analysis on Groups. New York: Wiley-Interscience. 1962. · Zbl 0107.09603
[20] Schipp, F., Wade, W. R., Simon, P.: Walsh Series. An Introduction to Dyadic Harmonic Analysis. Bristol and New York: Adam Hilger. 1990. · Zbl 0727.42017
[21] Sobol’, I. M.: The distribution of points in a cube and the approximate evaluation of integrals. ?. Vy?isl. Mat. i Mat. Fiz.7, 784-802 (1967) (Russian).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.