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
DOI: https://doi.org/10.1090/S0025-5718-01-01415-6
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. 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/.

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
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: https://doi.org/10.1090/S0025-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
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

American Mathematical Society