Mathematics of Computation

Author(s): Karl Entacher; Thomas Schell; Andreas Uhl.
Journal: Math. Comp. 71 (2002), 1231-1242.
MSC (2000): Primary 11Y40, 11-04; Secondary 11K45, 68W40
Posted: December 21, 2001
Retrieve article in: PDF
This article is available free of charge

Abstract: In the present paper we show how to speed up lattice parameter searches for Monte Carlo and quasi-Monte Carlo node sets. The classical measure for such parameter searches is the spectral test which is based on a calculation of the shortest nonzero vector in a lattice. Instead of the shortest vector we apply an approximation given by the LLL algorithm for lattice basis reduction. We empirically demonstrate the speed-up and the quality loss obtained by the LLL reduction, and we present important applications for parameter selections.

1.: L. Afflerbach, The sub-lattice structure of linear congruential random number generators, Manuscripta Mathematica 55 (1986), 455-465. MR 87k:65006
2.: J Ajtai, Generating Hard Instances of Lattice Problems, Report TR96-007, Electronic Colloquium on Computational Complexity ECCC, 1996, Web-page: [9].
3.: R.E. Caflisch, Monte Carlo and quasi-Monte Carlo methods, Acta Numer. 7 (1998), 1-49. MR 2000e:65019
4.: J Cai, Some Recent Progress on the Complexity of Lattice Problems, Report TR99-006, Electronic Colloquium on Computational Complexity ECCC, 1999, Web-page: [9].
5.: P. Coddington, Random Number Generators for Parallel Computers, NHSE Review, Second Issue, Northeast Parallel Architectures Center, 1996, Available at: http://nhse.cs.rice.edu/NHSEreview/RNG/.
6.: H. Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, 1993. MR 94i:11105
7.: R.R. Coveyou and R.D. MacPherson, Fourier analysis of uniform random number generators, J. Assoc. Comput. Mach. 14 (1967), 100-119. MR 36:4779
8.: U. Dieter, How to Calculate Shortest Vectors in a Lattice, Math. Comp. 29 (1975), no. 131, 827-833. MR 52:291
9.: ECCC, Electronic Colloquium on Computational Complexity ECCC, http://www.eccc.- uni-trier.de/eccc/.
10.: K. Entacher, A collection of selected pseudorandom number generators with linear structures - advanced version, Tech. report, Dept. of Mathematics, University Salzburg, Austria, available at: http://www.fh-sbg.ac.at/entacher, 1998, The previous version is published as technical report 97-1, ACPC-Austrian Center for Parallel Computation, University of Vienna, Austria, 1997.
11.: -, Parallel Streams of Linear Random Numbers in the Spectral Test, ACM Transactions on Modeling and Computer Simulation 9 (1999), no. 1, 31-44.
12.: K. Entacher, P. Hellekalek, and P. L'Ecuyer, Quasi-Monte Carlo Node Sets from Linear Congruential Generators, Monte Carlo and Quasi-Monte Carlo Methods 1998 (H. Niederreiter and J. Spanier, eds.), Springer, 2000, pp. 188-198.
13.: K. Entacher, A. Uhl, and S. Wegenkittl, Linear Congruential Generators for Parallel Monte-Carlo: the Leap-Frog Case., Monte Carlo Methods and Appl. 4 (1998), no. 1, 1-16. CMP 98:12
14.: U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp. 44 (1985), 463-471. MR 86e:11050
15.: G.S. Fishman, Monte Carlo: Concepts, Algorithms, and Applications, Springer Series in Operations Research, vol. 1, Springer, New York, 1996. MR 97g:65019
16.: P. Hellekalek, Don't Trust Parallel Monte Carlo, Twelfth Workshop on Parallel and Distributed Simultation PADS'98, May 26th - 29th (Banff, Alberta, Canada), IEEE Computer Society, Los Alamitos, California, 1998, pp. 82-89.
17.: P. Hellekalek and G. Larcher (eds.), Random and quasi-random point sets, Lecture Notes in Statistics, vol. 138, Springer, Berlin, 1998. MR 99g:11003
18.: F.J. Hickernell, Lattice Rules: How Well Do They Measure Up? In [17], pp. 109-166. MR 2000b:65007
19.: D.E. Knuth, The art of computer programming, 2nd ed., vol. 2: Seminumerical Algorithms, Addison-Wesley, Reading, MA, 1981. MR 83i:68003
20.: P. L'Ecuyer, Uniform random number generation, Ann. Oper. Res. 53 (1994), 77-120. MR 95k:65007
21.: -, Bad Lattice Structures for Vectors of Non-Successive Values Produced by Some Linear Recurrences, INFORMS Journal on Computing 9 (1997), 57-60. MR 98f:65014
22.: -, Random Number Generation, Handbook of Simulation, Chapter 4 (Jerry Banks, ed.), Wiley, 1998.
23.: -, Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure, Mathematics of Computation 68 (1999), no. 225, 249-260. MR 99c:11101
24.: P. L'Ecuyer and R. Couture, An Implementation of the Lattice and Spectral Tests for Multiple Recursive Linear Random Number Generators, INFORMS Journal on Computing 9 (1997), no. 2, 209-217. CMP 98:03
25.: P. L'Ecuyer and C. Lemieux, Variance Reduction via Lattice Rules, Management Science 46 (2000), no. 9, 1214-1235.
26.: C. Lemieux and P. L'Ecuyer, On selection criteria for lattice rules and other quasi-Monte Carlo point sets, Mathematics and Computers in Simulation 55 (2001), 139-148. CMP 2001:11
27.: A.K. Lenstra, H.W. Lenstra, and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen 261 (1982), 515-534. MR 84a:12002
28.: J. Leydold, H. Leeb, and W. Hörmann, Higher-Dimensional Properties of Non-Uniform Pseudo-Random Variates, In [33], pp. 341-355.
29.: G. Marsaglia, The structure of linear congruential sequences, Applications of Number Theory to Numerical Analysis (S. K. Zaremba, ed.), Academic Press, New York, 1972, pp. 248-285. MR 53:14854
30.: H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM, Philadelphia, 1992. MR 93h:65008
31.: H. Niederreiter, P. Hellekalek, G. Larcher, and P. Zinterhof (eds.), Monte Carlo and Quasi-Monte Carlo Methods 1996, Lecture Notes in Statistics, vol. 127, Springer, New York, 1998. MR 99d:65005
32.: H. Niederreiter and P.J.-S. Shiue (eds.), Monte Carlo and Quasi-Monte Carlo Methods in scientific computing, Lecture Notes in Statistics, vol. 106, Springer, New York, 1995. MR 97j:65002
33.: H. Niederreiter and J. Spanier (eds.), Monte Carlo and Quasi-Monte Carlo Methods 1998, Springer, Berlin, 2000.
34.: A.B. Owen, Monte Carlo extension of quasi-Monte Carlo, Proceedings of the 1998 Winter Simulation Conference (D.J. Madeiros, E.F. Watson, J.S. Carson, and M.S. Manivannan, eds.), 1998, Available from http://www.informs-cs.org/, pp. 571-577.
35.: M.E. Pohst, Computational algebraic number theory, DMV Seminar Band 21, Birkhäuser Verlag, 1993. MR 94j:11132
36.: B.D. Ripley, The lattice structure of pseudo-random number generators, Proc. Roy. Soc. London Ser. A 389 (1983), 197-204. MR 85i:65010
37.: V. Shoup, NTL: A Library for doing Number Theory, http://www.shoup.net/.
38.: I.H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford Univ. Press, New York, 1994. MR 98a:65026
39.: A. Storjohann, Faster Algorithms for Integer Lattice Basis Reduction, Technical report, Institute of Scientific Computing, ETH Zürich, 1996, Available at http://www.inf.ethz.ch/research/wr/.

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y40, 11-04, 11K45, 68W40

Karl Entacher
Affiliation: School of Telecommunications Engineering, University of Applied Sciences and Technologies, Schillerstr.~30, A-5020 Salzburg, Austria
Email: Karl.Entacher@fh-sbg.ac.at

Thomas Schell
Affiliation: Department of Scientific Computing, Salzburg University, Hellbrunnerstr.~34, A-5020 Salzburg, Austria

Andreas Uhl
Affiliation: Department of Scientific Computing, Salzburg University, Hellbrunnerstr.~34, A-5020 Salzburg, Austria

DOI: 10.1090/S0025-5718-01-01415-6
PII: S 0025-5718(01)01415-6
Keywords: Monte Carlo and quasi--Monte Carlo methods, lattice rules, good lattice points, random number generation, lattice basis reduction, LLL algorithm, Fincke-Pohst algorithm, spectral test
Received by editor(s): September 15, 2000
Posted: December 21, 2001
Additional Notes: The first author was supported by the Austrian Science Fund (FWF), pro. no. S8303-MAT, the second author by the FWF pro. no. P13732-MAT
Copyright of article: Copyright 2001, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS