Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

The tent transformation can improve the convergence rate of quasi-Monte Carlo algorithms using digital nets

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

In this paper we investigate multivariate integration in reproducing kernel Sobolev spaces for which the second partial derivatives are square integrable. As quadrature points for our quasi-Monte Carlo algorithm we use digital (t,m,s)-nets over\(\mathbb{Z}_2\) which are randomly digitally shifted and then folded using the tent transformation. For this QMC algorithm we show that the root mean square worst-case error converges with order\(2^{m(-2+\varepsilon)}\) for any ɛ >  0, where 2m is the number of points. A similar result for lattice rules has previously been shown by Hickernell.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Chrestenson H.E. (1955) A class of generalized Walsh functions. Pacific J. Math. 5, 17–31

    MathSciNet MATH  Google Scholar 

  2. Dick J., Kuo F.Y., Pillichshammer F., Sloan I.H. (2005) Construction algorithms for polynomial lattice rules for multivariate integration. Math. Comp. 74: 1895–1921

    Article MathSciNet MATH  Google Scholar 

  3. Dick J., Pillichshammer F. (2005) Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces. J. Complexity 21, 149–195

    Article MathSciNet MATH  Google Scholar 

  4. Dick J., Pillichshammer F. (2005) On the mean square weightedL2 discrepancy of randomized digital (t,m,s)-nets over\(\mathbb{Z}_2\). Acta Arith. 117, 371–403

    Article MathSciNet MATH  Google Scholar 

  5. Faure H. (1982) Discrépance de Suites Associées à un Système de Numération (en Dimensions). Acta Arith. 41, 337–351

    MathSciNet MATH  Google Scholar 

  6. Hickernell F.J. (2002) ObtainingO(N−2+ε) convergence for lattice quadrature rules. In: Fang K.T., Hickernell K.J., Niederreiter H. (eds) Monte Carlo and Quasi-Monte Carlo Methods 2000. Springer, Berlin Heidelberg New York, pp. 274–289

    Google Scholar 

  7. Matoušek J. (1999) Geometric Discrepancy Algorithms and Combinatorics, vol. 18. Springer, Berlin Heidelberg New York

  8. Niederreiter H. (1987) Point sets and sequences with small discrepancy. Monatsh. Math. 104, 273–337

    Article MathSciNet MATH  Google Scholar 

  9. Niederreiter H. Random Number Generation and Quasi-Monte Carlo Methods. CBMS–NSF Series in Applied Mathematics, vol. 63. SIAM, Philadelphia (1992)

  10. Niederreiter H. (1992) Low-discrepancy point sets obtained by digital constructions over finite fields. Czechoslovak Math. J. 42, 143–166

    MathSciNet MATH  Google Scholar 

  11. Niederreiter H. (1992) Finite fields, pseudorandom numbers, and quasirandom points. In: Mullen G.L., Shiue P.J.-S., (eds), Finite Fields, Coding Theory, and Advances in Communications and Computing. Dekker, New York, pp. 375–394

    Google Scholar 

  12. Niederreiter H. (2005) Constructions of (t,m,s)-nets and (t,s)-sequences. Finite Fields Appl. 11, 578–600

    Article MathSciNet MATH  Google Scholar 

  13. Owen A.B. (1995) Randomly permuted (t,m,s)-nets and (t,s)-sequences. Monte Carlo and quasi-Monte Carlo methods in scientific computing (Las Vegas, NV, 1994), Lecture Notes in Statistics vol. 106. Springer, Berlin Heidelberg New York, pp. 299–317

    Google Scholar 

  14. Pirsic G., Dick J., Pillichshammer F. (2006) Cyclic digital nets, hyperplane nets and multivariate integration in Sobolev spaces. SIAM J. Numer. Anal. 44, 385–411

    Article MathSciNet MATH  Google Scholar 

  15. Sloan I.H., Joe S. (1994) Lattice Methods for Multiple Integration. Clarendon Press, Oxford

    MATH  Google Scholar 

  16. Sloan I.H., Woźniakowski H. (1998) When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?. J. Complexity 14, 1–33

    Article MathSciNet MATH  Google Scholar 

  17. Sloan I.H., Woźniakowski H. (2001) Tractability of multivariate integration for weighted Korobov classes. J. Complexity 17, 697–721

    Article MathSciNet MATH  Google Scholar 

  18. Walsh J.L. (1923) A closed set of normal orthogonal functions. Am. J. Math. 55, 5–24

    Article  Google Scholar 

  19. Yue R.X., Hickernell F.J. (2002) The discrepancy and gain coefficients of scrambled digital nets. J. Complexity 18, 135–151

    Article MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Finanzmathematik, Universität Linz, Altenbergstraße 69, 4040, Linz, Austria

    Ligia L. Cristea, Gunther Leobacher & Friedrich Pillichshammer

  2. Division of Engineering, Science & Technology, UNSW Asia, 1 Kay Siang Road, Singapore, 248922, Singapore

    Josef Dick

Authors
  1. Ligia L. Cristea

    You can also search for this author inPubMed Google Scholar

  2. Josef Dick

    You can also search for this author inPubMed Google Scholar

  3. Gunther Leobacher

    You can also search for this author inPubMed Google Scholar

  4. Friedrich Pillichshammer

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toJosef Dick.

Additional information

Ligia L. Cristea is supported by the Austrian Research Fund (FWF), Project P 17022-N 12 and Project S 9609.

Josef Dick is supported by the Australian Research Council under its Center of Excellence Program.

Gunther Leobacher is supported by the Austrian Research Fund (FWF), Project S 8305.

Friedrich Pillichshammer is supported by the Austrian Research Fund (FWF), Project P 17022-N 12, Project S 8305 and Project S 9609.

Rights and permissions

About this article

Cite this article

Cristea, L.L., Dick, J., Leobacher, G.et al. The tent transformation can improve the convergence rate of quasi-Monte Carlo algorithms using digital nets.Numer. Math.105, 413–455 (2007). https://doi.org/10.1007/s00211-006-0046-x

Download citation

Mathematics Subject Classification (1991)

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp