QUASI MONTE CARLO INTEGRATION IN GRID ENVIRONMENTS: FURTHER LEAPING EFFECTS
Abstract
The splitting of Quasi-Monte Carlo (QMC) point sequences into interleaved substreams has been suggested to raise the speed of distributed numerical integration and to lower the traffic on the network. The usefulness of this approach in GRID environments is discussed. After specifying requirements for using QMC techniques in GRID environments in general we review and evaluate the proposals made in literature so far. In numerical integration experiments we investigate the quality of single leaped QMC point sequence substreams, comparing the respective properties of Sobol', Halton, Faure, Niederreiter-Xing, and Zinterhof sequences in detail. Numerical integration results obtained on a distributed system show that leaping sensitivity varies tremendously among the different sequences and we provide examples of deteriorated results caused by leaping effects, especially in heterogeneous settings which would be expected in GRID environments.
References
E. deDoncker , R. Zanny and K. Kaugars , Distributed numerical integration algorithms and applications, Proceedings of the 4th World Multiconference on Systemics, Cybernetics, and Informatics (SCI'00) (2000) pp. 244–249. Google Scholar-
A. R. Krommer and C. W. Überhuber , Numerical Integration on Advanced Computer Systems ,Lecture Notes in Computer Science 848 ( Springer , Berlin , 1994 ) . Crossref, Google Scholar -
A. R. Krommer and C. W. Überhuber , Computational integration ( SIAM , Philadelphia , 1998 ) . Crossref, Google Scholar - Parallel Algorithms and Applications 18(1–2), 13 (2003). Google Scholar
-
G. Evans , Practical numerical integration ( Wiley , Chichester , 1993 ) . Google Scholar -
H. Niederreiter , Random Number Generation and Quasi-Monte Carlo Methods ,CBMS-NSF Series in Applied Mathematics 63 ( SIAM , Philadelphia , 1992 ) . Crossref, Google Scholar - , Monte Carlo and Quasi-Monte Carlo Methods 1998, eds.
H. Niederreiter and J. Spanier (Springer, 2000) pp. 188–198. Crossref, Google Scholar S. Li , K. Kaugars and E. deDoncker , Grid-based numerical integration and visualization,Sixth International Conference on Computational Intelligence and Multimedia Applications (ICCIMA'05) (2005) (IEEE Computer Society Press, 2005) pp. 260–265. Google ScholarW. Ch. Schmid and A. Uhl , Parallel quasi-Monte Carlo integration using (t,s)-sequences, Parallel Computation. Proceedings of ACPC'99,Lecture Notes on Computer Science 1557 (Springer-Verlag, 1999) pp. 96–106. Google Scholar- Mathematics and Computers in Simulation 55, 249 (2001). Crossref, ISI, Google Scholar
- Parallel Algorithms and Applications 18(1–2), 27 (2003). Google Scholar
M. Mascagni and A. Karaivanova , A parallel quasi-Monte Carlo method for solving systems of linear equations,Lecture Notes in Computer Science 2330,The 2002 International Conference on Computational Science - ICCS 2002 (2002), eds.P. Sloot (Springer Verlag, Berlin, Germany, 2002) pp. 598–608. Google Scholar- , Monte Carlo and Quasi-Monte Carlo Methods 2000, eds.
K. T. Fang , F. J. Hickernell and H. Niederreiter (Springer-Verlag, 2002) pp. 369–380. Crossref, Google Scholar - Monte Carlo Methods and Applications 10(3-4), 213 (2004). Google Scholar
- Monte Carlo Methods and Appl. 11(1), 39 (2005). Crossref, Google Scholar
- J. W. L. Wan, K. Lai, A. W. Kolkiewicz, and K. S. Tan. A parallel quasi Monte Carlo approach to pricing multidimensional americal options. International Journal of High Performance Computing and Networking, 2006. To appear . Google Scholar
R. Schürer , Parallel high-dimensional integration: quasi-Monte Carlo versus adaptive cubature rules,Lecture Notes in Computer Science 2073,The 2001 International Conference on Computational Science - ICCS 2001 (2001), eds.V. N. Alexandrov (Springer Verlag, Berlin, Germany, 2001) pp. 1262–1271. Google Scholar- Journal of Parallel and Distributed Computing 38, 101 (1996). Crossref, ISI, Google Scholar
- Parallel Computing 26(5), 641 (2000). Crossref, ISI, Google Scholar
- Computing Science and Statistics 30 (1999). Google Scholar
E. deDoncker , Distributed quasi-Monte Carlo methods in a heterogeneous environment, Proceedings of the Heterogeneous Computing Workshop 2000 (HCW'2000) (IEEE Computer Society Press, 2000) pp. 200–206. Google ScholarE. deDoncker , Asynchronous quasi-Monte Carlo methods, Proceedings of the High Performance Computing Symposium 2000 (HPC'00) (2000) pp. 130–135. Google ScholarL. Cucos and E. deDoncker , Distributed QMC algorithms: new strategies for and performance evaluation, Proceedings of the High Performance Computing Symposium 2002 (HPC'02)/Advanced Simulation Techniques Conference (2002) pp. 155–159. Google Scholar- , Monte Carlo and Quasi-Monte Carlo Methods 2000, eds.
K. T. Fang , F. J. Hickernell and H. Niederreiter (Springer-Verlag, 2002) pp. 406–421. Crossref, Google Scholar -
A. Srinivasan , Parallel and distributed computing issues in pricing financial derivatives through quasi-Monte Carlo , Proceedings of the International Parallel & Distributed Processing Symposium 2002 (IPDPS'02) ( IEEE Computer Society Press ) . Google Scholar - Journal of Complexity 19, 259 (2003). Crossref, ISI, Google Scholar
Peter Zinterhof , High dimensional improper integration procedures. In Civil Engineering Faculty Technical University of Košice, Proceedings of Contributions of the 7th International Scientific Conference (TULIP, Hroncova 5, 04001 Košice, SLOVAKIA, 2002) pp. 109–115. Google Scholar- Rudolf Schürer and Wolfgang Ch. Schmid. Mint - the database of optimal (t,m,s)-net parameters. online: http://mint.sbg.ac.at/ . Google Scholar
- U.S.S.R. Computational Mathematics and Mathematical Physics 7(4), 86 (1967). Crossref, Google Scholar
- Monatshefte für Mathematik 104, 273 (1987). Crossref, ISI, Google Scholar
- , Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing,
Lecture Notes in Statistics 106, eds.Harald Niederreiter and P. J.-S. Shiue (Springer-Verlag, 1995) pp. 58–86. Crossref, Google Scholar - Acta Arithmetica 41, 337 (1982). Crossref, ISI, Google Scholar
- J. H. Halton. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimension integrals. Numer. Math., 2:84–90, 1960. Berichtigung, ibid., (1960), p. 196 . Google Scholar
- Finite Fields and Their Applications 2, 241 (1996). Crossref, Google Scholar
- Acta Arithmetica 71(1), 87 (1995). Google Scholar
- Journal of Combinatorial Designs 7, 381 (1999). Crossref, ISI, Google Scholar
- Sitzungsberichte der Österreichischen Akademie der Wissenschaften, math.-nat.wiss. Klasse Abt. II 177, 51 (1969). Google Scholar
- Soviet Math. Dokl. 14(3), 734 (1973). Google Scholar
- ACM Transactions on Mathematical Software 23(2), 266 (1997). Crossref, ISI, Google Scholar
- Monte Carlo Methods and Appl. 2(1), 1 (1996). Crossref, Google Scholar
- Jürgen Hartinger, Reinhold Kaindorfer, and Volker Ziegler. On the corner avoidance properties of various low-discrepancy sequences. 2004. submitted . Google Scholar
- Art B. Owen. Halton sequences avoid the origin. Technical report, Stanford University, 2004 . Google Scholar


