An algorithm for QMC integration using low-discrepancy lattice sets

Vojtěch Franěk

Commentationes Mathematicae Universitatis Carolinae (2008)

  • Volume: 49, Issue: 3, page 447-462
  • ISSN: 0010-2628

Abstract

top
Many low-discrepancy sets are suitable for quasi-Monte Carlo integration. Skriganov showed that the intersections of suitable lattices with the unit cube have low discrepancy. We introduce an algorithm based on linear programming which scales any given lattice appropriately and computes its intersection with the unit cube. We compare the quality of numerical integration using these low-discrepancy lattice sets with approximations using other known (quasi-)Monte Carlo methods. The comparison is based on several numerical experiments, where we consider both the precision of the approximation and the speed of generating the sets. We conclude that up to dimensions about 15, low-discrepancy lattices yield fairly good results. In higher dimensions, our implementation of the computation of the intersection takes too long and ceases to be feasible.

How to cite

top

Franěk, Vojtěch. "An algorithm for QMC integration using low-discrepancy lattice sets." Commentationes Mathematicae Universitatis Carolinae 49.3 (2008): 447-462. <http://eudml.org/doc/250296>.

@article{Franěk2008,
abstract = {Many low-discrepancy sets are suitable for quasi-Monte Carlo integration. Skriganov showed that the intersections of suitable lattices with the unit cube have low discrepancy. We introduce an algorithm based on linear programming which scales any given lattice appropriately and computes its intersection with the unit cube. We compare the quality of numerical integration using these low-discrepancy lattice sets with approximations using other known (quasi-)Monte Carlo methods. The comparison is based on several numerical experiments, where we consider both the precision of the approximation and the speed of generating the sets. We conclude that up to dimensions about 15, low-discrepancy lattices yield fairly good results. In higher dimensions, our implementation of the computation of the intersection takes too long and ceases to be feasible.},
author = {Franěk, Vojtěch},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {QMC integration; lattices; discrepancy; QMC integration; lattices; quasi-Monte Carlo method; numerical experiments; linear programming method; discrepancy},
language = {eng},
number = {3},
pages = {447-462},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {An algorithm for QMC integration using low-discrepancy lattice sets},
url = {http://eudml.org/doc/250296},
volume = {49},
year = {2008},
}

TY - JOUR
AU - Franěk, Vojtěch
TI - An algorithm for QMC integration using low-discrepancy lattice sets
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2008
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 49
IS - 3
SP - 447
EP - 462
AB - Many low-discrepancy sets are suitable for quasi-Monte Carlo integration. Skriganov showed that the intersections of suitable lattices with the unit cube have low discrepancy. We introduce an algorithm based on linear programming which scales any given lattice appropriately and computes its intersection with the unit cube. We compare the quality of numerical integration using these low-discrepancy lattice sets with approximations using other known (quasi-)Monte Carlo methods. The comparison is based on several numerical experiments, where we consider both the precision of the approximation and the speed of generating the sets. We conclude that up to dimensions about 15, low-discrepancy lattices yield fairly good results. In higher dimensions, our implementation of the computation of the intersection takes too long and ceases to be feasible.
LA - eng
KW - QMC integration; lattices; discrepancy; QMC integration; lattices; quasi-Monte Carlo method; numerical experiments; linear programming method; discrepancy
UR - http://eudml.org/doc/250296
ER -

References

top
  1. Beck J., Chen W.L., Irregularities of Distribution, Cambridge University Press, Cambridge, 1987. Zbl1156.11029MR0903025
  2. Cranley R., Patterson T.N.L., 10.1137/0713071, SIAM J. Numer. Anal. 13 (1976), 6 909-914. (1976) Zbl0354.65016MR0494820DOI10.1137/0713071
  3. Davis P.J., Rabinowitz P., Methods of Numerical Integration, 2nd edition, Academic Press Inc., Orlando FL, 1984. Zbl1139.65016MR0760629
  4. Faure H., Discrepancy of sequences associated with a number system (in dimension s ), Acta Arith. 41 (1982), 4 337-351. (1982) MR0677547
  5. Genz A., Testing multidimensional integration routines, in Tools, Methods and Languages for Scientific and Engineering Computation, B. Ford, J. C. Rault and F. Thomasset, Eds., North-Holland, Amsterdam, 1984. 
  6. Hua L.K., Wang Y., Applications of Number Theory to Numerical Analysis, Springer, Berlin, 1981. Zbl0465.10045MR0617192
  7. Janse van Rensburg E.J., Torrie G.M., 10.1088/0305-4470/26/4/022, J. Phys. A 26 (1993), 943-953. (1993) Zbl0781.65015MR1211087DOI10.1088/0305-4470/26/4/022
  8. L'Ecuyer P., Lemieux C., Variance reduction via lattice rules, in Management Science 49-6 (2000), 1214-1235. (2000) 
  9. Lovász L., An algorithmic theory of numbers, graphs and convexity, CBMS-NSF Regional Conference Series in Applied Mathematics 50, SIAM, Philadelphia, Pennsylvania, 1986. MR0861822
  10. Matoušek J., Geometric Discrepancy: An Illustrated Guide, Springer, Berlin, 1999. MR1697825
  11. Matoušek J., 10.1006/jcom.1998.0489, J. Complexity 14 (1998), 527-556. (1998) MR1659004DOI10.1006/jcom.1998.0489
  12. Niederreiter H., Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics 63, SIAM, Philadelphia, Pennsylvania, 1992. Zbl0761.65002MR1172997
  13. Owen A.B., Randomly permuted ( t , m , s ) -nets and ( t , s ) -sequences, in Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Harald Niederreiter and Peter Jau-Shyong Shiue, Eds., Springer, New York, 1995, pp. 299-317. Zbl0831.65024MR1445791
  14. Owen A.B., 10.1214/aos/1031594731, Ann. Statist. 25 (1997), 4 1541-1562. (1997) MR1463564DOI10.1214/aos/1031594731
  15. Owen A.B., 10.1137/S0036142994277468, SIAM J. Numer. Anal. 34 (1997), 5 1884-1910. (1997) Zbl0890.65023MR1472202DOI10.1137/S0036142994277468
  16. Radovic I., Sobol' I.M., Tichy R.F., Quasi-Monte Carlo methods for numerical integration: Comparison of different low-discrepancy sequences, Monte Carlo Methods Appl. 2 (1996), 1-14. (1996) Zbl0851.65015MR1395313
  17. Roos P., Arnold L., Numerische Experimente zur mehrdimensionalen Quadratur, Österreich. Akad. Wiss. Math.-Natur. Kl. S.-B. II 172 (1963), 271-286. (1963) Zbl0128.36902MR0170475
  18. Skriganov M.M., Constructions of uniform distributions in terms of geometry of numbers, Algebra i Analiz 6 (1994), 200-230. (1994) Zbl0840.11041MR1301838
  19. Sloan I.H., Joe S., Lattice Method for Multiple Integration, Clarendon Press, Oxford University Press, New York, 1994. MR1442955
  20. Sloan I.H., Kuo F.Y., Joe S., 10.1137/S0036142901393942, SIAM J. Numer. Anal. 40 (2002), 1650-1665. (2002) Zbl1037.65005MR1950616DOI10.1137/S0036142901393942
  21. Sloan I.H., Kuo F.Y., Joe S., 10.1090/S0025-5718-02-01420-5, Math. Comp. 71 (2002), 1609-1640. (2002) Zbl1011.65001MR1933047DOI10.1090/S0025-5718-02-01420-5
  22. Spanier J., Maize E.H., 10.1137/1036002, SIAM Review 36 1 (1994), 18-44. (1994) Zbl0824.65009MR1267048DOI10.1137/1036002
  23. Tezuka S., Uniform Random Numbers. Theory and Practice, Kluwer Academic Publishers, Dordrecht, 1995. Zbl0841.65004

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.