| Title:
|
An algorithm for QMC integration using low-discrepancy lattice sets (English) |
| Author:
|
Franěk, Vojtěch |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
49 |
| Issue:
|
3 |
| Year:
|
2008 |
| Pages:
|
447-462 |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
QMC integration |
| Keyword:
|
lattices |
| Keyword:
|
discrepancy |
| MSC:
|
65C05 |
| MSC:
|
65D30 |
| idZBL:
|
Zbl 1212.65008 |
| idMR:
|
MR2490439 |
| . |
| Date available:
|
2009-05-05T17:12:19Z |
| Last updated:
|
2013-09-22 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119735 |
| . |
| Reference:
|
[1] Beck J., Chen W.L.: Irregularities of Distribution.Cambridge University Press, Cambridge, 1987. Zbl 1156.11029, MR 0903025 |
| Reference:
|
[2] Cranley R., Patterson T.N.L.: Randomization of number theoretic methods for multiple integration.SIAM J. Numer. Anal. 13 (1976), 6 909-914. Zbl 0354.65016, MR 0494820, 10.1137/0713071 |
| Reference:
|
[3] Davis P.J., Rabinowitz P.: Methods of Numerical Integration.2nd edition, Academic Press Inc., Orlando FL, 1984. Zbl 1139.65016, MR 0760629 |
| Reference:
|
[4] Faure H.: Discrepancy of sequences associated with a number system (in dimension $s$).Acta Arith. 41 (1982), 4 337-351. MR 0677547 |
| Reference:
|
[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. |
| Reference:
|
[6] Hua L.K., Wang Y.: Applications of Number Theory to Numerical Analysis.Springer, Berlin, 1981. Zbl 0465.10045, MR 0617192 |
| Reference:
|
[7] Janse van Rensburg E.J., Torrie G.M.: Estimation of multidimensional integrals: is Monte Carlo the best method?.J. Phys. A 26 (1993), 943-953. Zbl 0781.65015, MR 1211087, 10.1088/0305-4470/26/4/022 |
| Reference:
|
[8] L'Ecuyer P., Lemieux C.: Variance reduction via lattice rules.in Management Science 49-6 (2000), 1214-1235. |
| Reference:
|
[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. MR 0861822 |
| Reference:
|
[10] Matoušek J.: Geometric Discrepancy: An Illustrated Guide.Springer, Berlin, 1999. MR 1697825 |
| Reference:
|
[11] Matoušek J.: On the $L_2$-discrepancy for anchored boxes.J. Complexity 14 (1998), 527-556. MR 1659004, 10.1006/jcom.1998.0489 |
| Reference:
|
[12] Niederreiter H.: Random number generation and quasi-Monte Carlo methods.CBMS-NSF Regional Conference Series in Applied Mathematics 63, SIAM, Philadelphia, Pennsylvania, 1992. Zbl 0761.65002, MR 1172997 |
| Reference:
|
[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. Zbl 0831.65024, MR 1445791 |
| Reference:
|
[14] Owen A.B.: Scrambled net variance for integrals of smooth functions.Ann. Statist. 25 (1997), 4 1541-1562. MR 1463564, 10.1214/aos/1031594731 |
| Reference:
|
[15] Owen A.B.: Monte-Carlo variance of scrambled net quadrature.SIAM J. Numer. Anal. 34 (1997), 5 1884-1910. Zbl 0890.65023, MR 1472202, 10.1137/S0036142994277468 |
| Reference:
|
[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. Zbl 0851.65015, MR 1395313 |
| Reference:
|
[17] Roos P., Arnold L.: Numerische Experimente zur mehrdimensionalen Quadratur.Österreich. Akad. Wiss. Math.-Natur. Kl. S.-B. II 172 (1963), 271-286. Zbl 0128.36902, MR 0170475 |
| Reference:
|
[18] Skriganov M.M.: Constructions of uniform distributions in terms of geometry of numbers.Algebra i Analiz 6 (1994), 200-230. Zbl 0840.11041, MR 1301838 |
| Reference:
|
[19] Sloan I.H., Joe S.: Lattice Method for Multiple Integration.Clarendon Press, Oxford University Press, New York, 1994. MR 1442955 |
| Reference:
|
[20] Sloan I.H., Kuo F.Y., Joe S.: Constructing randomly shifted lattice rules in weighted Sobolev spaces.SIAM J. Numer. Anal. 40 (2002), 1650-1665. Zbl 1037.65005, MR 1950616, 10.1137/S0036142901393942 |
| Reference:
|
[21] Sloan I.H., Kuo F.Y., Joe S.: On the step-by-step construction of quasi-Monte Carlo integration rules that achieve strong tractability error bounds in weighted Sobolev spaces.Math. Comp. 71 (2002), 1609-1640. Zbl 1011.65001, MR 1933047, 10.1090/S0025-5718-02-01420-5 |
| Reference:
|
[22] Spanier J., Maize E.H.: Quasi-random methods for estimating integrals using relatively small samples.SIAM Review 36 1 (1994), 18-44. Zbl 0824.65009, MR 1267048, 10.1137/1036002 |
| Reference:
|
[23] Tezuka S.: Uniform Random Numbers. Theory and Practice.Kluwer Academic Publishers, Dordrecht, 1995. Zbl 0841.65004 |
| . |
