Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The asymptotic efficiency
of randomized nets for quadrature

Authors: Fred J. Hickernell and Hee Sun Hong
Journal: Math. Comp. 68 (1999), 767-791
MSC (1991): Primary 65D30, 65D32
MathSciNet review: 1609662
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An $ \mathcal{L}_{2}$-type discrepancy arises in the average- and worst-case error analyses for multidimensional quadrature rules. This discrepancy is uniquely defined by $ K(x,y)$, which serves as the covariance kernel for the space of random functions in the average-case analysis and a reproducing kernel for the space of functions in the worst-case analysis. This article investigates the asymptotic order of the root mean square discrepancy for randomized $(0,m,s)$-nets in base $b$. For moderately smooth $ K(x,y)$ the discrepancy is $ \operatorname{O}(N^{-1}[\log(N)]^{(s-1)/2})$, and for $ K(x,y)$ with greater smoothness the discrepancy is $ \operatorname{O}(N^{-3/2}[\operatorname{log}(N)]^{(s-1)/2})$, where $N=b^{m}$ is the number of points in the net. Numerical experiments indicate that the $(t,m,s)$-nets of Faure, Niederreiter and Sobol' do not necessarily attain the higher order of decay for sufficiently smooth kernels. However, Niederreiter nets may attain the higher order for kernels corresponding to spaces of periodic functions.

References [Enhancements On Off] (What's this?)

  • [AS64] M. Abramowitz and I. A. Stegun (eds.), Handbook of mathematical functions with formulas, graphs and mathematical tables, U. S. Government Printing Office, Washington, DC, 1964. MR 29:4914
  • [BF88] P. Bratley and B. L. Fox, Algorithm 659: Implementing Sobol's quasirandom sequence generator, ACM Trans. Math. Softw. 14 (1988), 88-100.
  • [BFN92] P. Bratley, B. L. Fox, and H. Niederreiter, Implementation and tests of low-discrepancy sequences, ACM Trans. Model. Comput. Simul. 2 (1992), 195-213.
  • [Ent96] K. Entacher, Generalized Haar function systems in the theory of uniform distribution modulo one, Ph.D. thesis, University of Salzburg, 1996.
  • [Fau82] H. Faure, Discrépance de suites associées à un système de numération (en dimension s), Acta Arith. 41 (1982), 337-351. MR 84m:10050
  • [Gen92] A. Genz, Numerical computation of multivariate normal probabilities, J. Comput. Graph. Statist. 1 (1992), 141-150.
  • [Hic95] F. J. Hickernell, A comparison of random and quasirandom points for multidimensional quadrature, Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (H. Niederreiter and P. J.-S. Shiue, eds.), Lecture Notes in Statistics, vol. 106, Springer-Verlag, New York, 1995, pp. 213-227. MR 97j:65002
  • [Hic96a] F. J. Hickernell, The mean square discrepancy of randomized nets, ACM Trans. Model. Comput. Simul. 6 (1996), 274-296.
  • [Hic96b] F. J. Hickernell, Quadrature error bounds with applications to lattice rules, SIAM J. Numer. Anal. 33 (1996), 1995-2016. MR 97m:65050
  • [Hic98] F. J. Hickernell, A generalized discrepancy and quadrature error bound, Math. Comp. 67 (1998), 299-322. MR 98c:65032
  • [HW81] L. K. Hua and Y. Wang, Applications of number theory to numerical analysis, Springer-Verlag, Berlin, and Science Press, Beijing, 1981. MR 83g:10034
  • [LSW94] G. Larcher, W. Ch. Schmid, and R. Wolf, Representation of functions as Walsh series to different bases and an application to the numerical integration of high-dimensional Walsh series., Math. Comp. 63 (1994), 701-716. MR 95a:65045
  • [LT94] G. Larcher and C. Traunfellner, On the numerical integration of Walsh series by number-theoretic methods, Math. Comp. 63 (1994), 277-291. MR 94j:65030
  • [MC94] W. J. Morokoff and R. E. Caflisch, Quasi-random sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), 1251-1279. MR 95e:65009
  • [Nie92] H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM, Philadelphia, 1992. MR 93h:65008
  • [Owe95] A. B. Owen, Randomly permuted $(t,m,s)$-nets and $(t,s)$-sequences, Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (H. Niederreiter and P. J.-S. Shiue, eds.), Lecture Notes in Statistics, vol. 106, Springer-Verlag, New York, 1995, pp. 299-317. MR 97k:65013
  • [Owe97a] A. B. Owen, Monte Carlo variance of scrambled equidistribution quadrature, SIAM J. Numer. Anal. 34 (1997), 1884-1910. CMP 98:01
  • [Owe97b] A. B. Owen, Scrambled net variance for integrals of smooth functions, Ann. Stat. 25 (1997), 1541-1562. CMP 97:16
  • [Rit95] K. Ritter, Average case analysis of numerical problems, Ph.D. thesis, Universität Erlangen-Nürnberg, Erlangen, Germany, 1995.
  • [Sai88] S. Saitoh, Theory of reproducing kernels and its applications, Longman Scientific & Technical, Essex, England, 1988. MR 90f:46045
  • [SJ94] I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford University Press, Oxford, 1994. MR 98a:65026
  • [Ton90] Y. L. Tong, The multivariate normal distribution, Springer-Verlag, New York, 1990. MR 91g:60021
  • [Wah90] G. Wahba, Spline models for observational data, SIAM, Philadelphia, 1990. MR 91g:62028
  • [Was93] G. W. Wasilkowski, Integration and approximation of multivariate functions: Average case complexity with isotropic Wiener measure, Bull. Amer. Math. Soc. 28 (1993), 308-314. MR 93i:65136
  • [Wo\'{z}91] H. Wo\'{z}niakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. 24 (1991), 185-194. MR 91i:65224
  • [Zar68] S. K. Zaremba, Some applications of multidimensional integration by parts, Ann. Polon. Math. 21 (1968), 85-96. MR 38:4034

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 65D30, 65D32

Retrieve articles in all journals with MSC (1991): 65D30, 65D32

Additional Information

Fred J. Hickernell
Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong

Hee Sun Hong
Affiliation: Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong

Keywords: $\mathcal{L}_{2}$-discrepancy, multidimensional integration, $(t, m, s)$-nets, number-theoretic nets and sequences
Received by editor(s): March 6, 1997
Received by editor(s) in revised form: September 11, 1997
Additional Notes: This research was supported by a HKBU FRG grant 95-96/II-01.
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society