×

zbMATH — the first resource for mathematics

Construction algorithms for higher order polynomial lattice rules. (English) Zbl 1218.65003
Summary: Higher order polynomial lattice point sets are special types of digital higher order nets which are known to achieve almost optimal convergence rates when used in a quasi-Monte Carlo algorithm to approximate high-dimensional integrals over the unit cube. The existence of higher order polynomial lattice point sets of “good” quality has recently been established, but their construction was not addressed.
We use a component-by-component approach to construct higher order polynomial lattice rules achieving optimal convergence rates for functions of arbitrarily high smoothness and at the same time-under certain conditions on the weights-(strong) polynomial tractability. Combining this approach with a sieve-type algorithm yields higher order polynomial lattice rules adjusting themselves to the smoothness of the integrand up to a certain given degree. Higher order Korobov polynomial lattice rules achieve analogous results.

MSC:
65D30 Numerical integration
11K45 Pseudo-random numbers; Monte Carlo methods
65C05 Monte Carlo methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J. Baldeaux, J. Dick, G. Leobacher, D. Nuyens, F. Pillichshammer, Fast construction of higher order polynomial lattice rules (in preparation). · Zbl 1244.65002
[2] Chrestenson, H.E., A class of generalized Walsh functions, Pacific J. math., 5, 17-31, (1955) · Zbl 0065.05302
[3] Dick, J., Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order, SIAM J. numer. anal., 46, 1519-1553, (2008) · Zbl 1189.42012
[4] Dick, J., The construction of extensible polynomial lattice rules with small weighted star discrepancy, Math. comp., 76, 2077-2085, (2007) · Zbl 1135.11039
[5] Dick, J., Explicit constructions of quasi-Monte Carlo rules for the numerical integration of high-dimensional periodic functions, SIAM J. numer. anal., 45, 2141-2176, (2007) · Zbl 1158.65007
[6] Dick, J., The decay of the Walsh coefficients of smooth functions, Bull. austral. math. soc., 80, 430-453, (2009) · Zbl 1183.42027
[7] Dick, J.; Kritzer, P.; Pillichshammer, F.; Schmid, W.Ch., On the existence of higher order polynomial lattices based on a generalized figure of merit, J. complexity, 23, 581-593, (2007) · Zbl 1130.65047
[8] Dick, J.; Kuo, F.; Pillichshammer, F.; Sloan, I.H., Construction algorithms for polynomial lattice rules for multivariate integration, Math. comp., 74, 1895-1921, (2005) · Zbl 1079.65007
[9] Dick, J.; Pillichshammer, F., Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules, J. complexity, 23, 436-453, (2007) · Zbl 1130.65005
[10] Dick, J.; Pillichshammer, F., Digital nets and sequences. discrepancy theory and quasi-Monte Carlo integration, (2010), Cambridge University Press Cambridge · Zbl 1282.65012
[11] Dick, J.; Pillichshammer, F., Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces, J. complexity, 21, 149-195, (2005) · Zbl 1085.41021
[12] Dick, J.; Pillichshammer, F.; Waterhouse, B., The construction of good extensible rank-1 lattices, Math. comp., 77, 2345-2373, (2008) · Zbl 1211.11092
[13] Korobov, N.M., Properties and calculation of optimal coefficients, Dokl. akad. nauk. SSSR, 132, 1009-1012, (1960), (in Russian) · Zbl 0094.11204
[14] Niederreiter, H., ()
[15] Niederreiter, H., Point sets and sequences with small discrepancy, Monatsh. math., 104, 273-337, (1987) · Zbl 0626.10045
[16] Niederreiter, H., Low-discrepancy point sets obtained by digital constructions over finite fields, Czechoslovak math. J., 42, 143-166, (1992) · Zbl 0757.11024
[17] Sloan, I.H.; Joe, S., Lattice methods for multiple integration, (1994), Oxford Science Publications, The Clarendon Press, Oxford University Press New York · Zbl 0855.65013
[18] Sloan, I.H.; Reztsov, A., Component-by-component construction of good lattice rules, Math. comp., 71, 263-273, (2002) · Zbl 0985.65018
[19] Sloan, I.H.; Wo┼║niakowski, H., When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?, J. complexity, 14, 1-33, (1998) · Zbl 1032.65011
[20] Walsh, J.L., A closed set of normal orthogonal functions, Amer. J. math., 45, 5-24, (1923) · JFM 49.0293.03
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.