Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Efficient lattice assessment for LCG and GLP parameter searches

Authors: Karl Entacher, Thomas Schell and Andreas Uhl
Journal: Math. Comp. 71 (2002), 1231-1242
MSC (2000): Primary 11Y40, 11-04; Secondary 11K45, 68W40
Published electronically: December 21, 2001
MathSciNet review: 1898753
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

  • 1. Lothar Afflerbach, The sub-lattice structure of linear congruential random number generators, Manuscripta Math. 55 (1986), no. 3-4, 455–465. MR 836877, 10.1007/BF01186658
  • 2. J Ajtai, Generating Hard Instances of Lattice Problems, Report TR96-007, Electronic Colloquium on Computational Complexity ECCC, 1996, Web-page: [9].
  • 3. Russel E. Caflisch, Monte Carlo and quasi-Monte Carlo methods, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 1–49. MR 1689431, 10.1017/S0962492900002804
  • 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:
  • 6. Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206
  • 7. R. R. Coveyou and R. D. Macpherson, Fourier analysis of uniform random number generators, J. Assoc. Comput. Mach. 14 (1967), 100–119. MR 0221727
  • 8. U. Dieter, How to calculate shortest vectors in a lattice, Math. Comp. 29 (1975), 827–833. MR 0379386, 10.1090/S0025-5718-1975-0379386-6
  • 9. ECCC, Electronic Colloquium on Computational Complexity ECCC, http://www.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:, 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), no. 170, 463–471. MR 777278, 10.1090/S0025-5718-1985-0777278-8
  • 15. George S. Fishman, Monte Carlo, Springer Series in Operations Research, Springer-Verlag, New York, 1996. Concepts, algorithms, and applications. MR 1392474
  • 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. Peter Hellekalek and Gerhard Larcher (eds.), Random and quasi-random point sets, Lecture Notes in Statistics, vol. 138, Springer-Verlag, New York, 1998. MR 1662838
  • 18. Fred J. Hickernell, Lattice rules: how well do they measure up?, Random and quasi-random point sets, Lecture Notes in Statist., vol. 138, Springer, New York, 1998, pp. 109–166. MR 1662841, 10.1007/978-1-4612-1702-2_3
  • 19. Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
  • 20. Pierre L’Ecuyer, Uniform random number generation, Ann. Oper. Res. 53 (1994), 77–120. Simulation and modeling. MR 1310607, 10.1007/BF02136827
  • 21. Pierre L’Ecuyer, Bad lattice structures for vectors of nonsuccessive values produced by some linear recurrences, INFORMS J. Comput. 9 (1997), no. 1, 57–60. MR 1478040, 10.1287/ijoc.9.1.57
  • 22. -, Random Number Generation, Handbook of Simulation, Chapter 4 (Jerry Banks, ed.), Wiley, 1998.
  • 23. Pierre L’Ecuyer, Tables of linear congruential generators of different sizes and good lattice structure, Math. Comp. 68 (1999), no. 225, 249–260. MR 1489972, 10.1090/S0025-5718-99-00996-5
  • 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 Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, 10.1007/BF01457454
  • 28. J. Leydold, H. Leeb, and W. Hörmann, Higher-Dimensional Properties of Non-Uniform Pseudo-Random Variates, In [33], pp. 341-355.
  • 29. George Marsaglia, The structure of linear congruential sequences, Applications of number theory to numerical analysis (Proc. Sympos., Univ. Montreal, Montreal, Que., 1971) Academic Press, New York, 1972, pp. 249–285. MR 0411115
  • 30. Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997
  • 31. Harald Niederreiter, Peter Hellekalek, Gerhard Larcher, and Peter Zinterhof (eds.), Monte Carlo and quasi-Monte Carlo methods 1996, Lecture Notes in Statistics, vol. 127, Springer-Verlag, New York, 1998. MR 1644508
  • 32. Harald Niederreiter and Peter Jau-Shyong Shiue (eds.), Monte Carlo and quasi-Monte Carlo methods in scientific computing, Lecture Notes in Statistics, vol. 106, Springer-Verlag, New York, 1995. MR 1445777
  • 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, pp. 571-577.
  • 35. Michael E. Pohst, Computational algebraic number theory, DMV Seminar, vol. 21, Birkhäuser Verlag, Basel, 1993. MR 1243639
  • 36. B. D. Ripley, The lattice structure of pseudorandom number generators, Proc. Roy. Soc. London Ser. A 389 (1983), no. 1796, 197–204. MR 719645
  • 37. V. Shoup, NTL: A Library for doing Number Theory,
  • 38. I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1994. MR 1442955
  • 39. A. Storjohann, Faster Algorithms for Integer Lattice Basis Reduction, Technical report, Institute of Scientific Computing, ETH Zürich, 1996, Available at

Similar Articles

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

Retrieve articles in all journals with MSC (2000): 11Y40, 11-04, 11K45, 68W40

Additional Information

Karl Entacher
Affiliation: School of Telecommunications Engineering, University of Applied Sciences and Technologies, Schillerstr. 30, A-5020 Salzburg, Austria

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

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
Published electronically: 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
Article copyright: © Copyright 2001 American Mathematical Society