Efficient lattice assessment for LCG and GLP parameter searches

Entacher, Karl; Schell, Thomas; Uhl, Andreas

doi:10.1090/S0025-5718-01-01415-6

Efficient lattice assessment for LCG and GLP parameter searches
HTML articles powered by AMS MathViewer

by Karl Entacher, Thomas Schell and Andreas Uhl PDF

Math. Comp. 71 (2002), 1231-1242 Request permission

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

Lothar Afflerbach, The sub-lattice structure of linear congruential random number generators, Manuscripta Math. 55 (1986), no. 3-4, 455–465. MR 836877, DOI 10.1007/BF01186658
J Ajtai, Generating Hard Instances of Lattice Problems, Report TR96-007, Electronic Colloquium on Computational Complexity ECCC, 1996, Web-page: [ECCC, Electronic Colloquium on Computational Complexity ECCC, http://www.eccc.uni-trier.de/eccc/].
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, DOI 10.1017/S0962492900002804
J Cai, Some Recent Progress on the Complexity of Lattice Problems, Report TR99-006, Electronic Colloquium on Computational Complexity ECCC, 1999, Web-page: [ECCC, Electronic Colloquium on Computational Complexity ECCC, http://www.eccc.uni-trier.de/eccc/].
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/.
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
R. R. Coveyou and R. D. Macpherson, Fourier analysis of uniform random number generators, J. Assoc. Comput. Mach. 14 (1967), 100–119. MR 221727, DOI 10.1145/321371.321379
U. Dieter, How to calculate shortest vectors in a lattice, Math. Comp. 29 (1975), 827–833. MR 379386, DOI 10.1090/S0025-5718-1975-0379386-6
ECCC, Electronic Colloquium on Computational Complexity ECCC, http://www.eccc.uni-trier.de/eccc/.
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.
—, Parallel Streams of Linear Random Numbers in the Spectral Test, ACM Transactions on Modeling and Computer Simulation 9 (1999), no. 1, 31–44.
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.
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.
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, DOI 10.1090/S0025-5718-1985-0777278-8
George S. Fishman, Monte Carlo, Springer Series in Operations Research, Springer-Verlag, New York, 1996. Concepts, algorithms, and applications. MR 1392474, DOI 10.1007/978-1-4757-2553-7
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.
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, DOI 10.1007/978-1-4612-1702-2
Fred J. Hickernell, Lattice rules: how well do they measure up?, Random and quasi-random point sets, Lect. Notes Stat., vol. 138, Springer, New York, 1998, pp. 109–166. MR 1662841, DOI 10.1007/978-1-4612-1702-2_{3}
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
Pierre L’Ecuyer, Uniform random number generation, Ann. Oper. Res. 53 (1994), 77–120. Simulation and modeling. MR 1310607, DOI 10.1007/BF02136827
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, DOI 10.1287/ijoc.9.1.57
—, Random Number Generation, Handbook of Simulation, Chapter 4 (Jerry Banks, ed.), Wiley, 1998.
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, DOI 10.1090/S0025-5718-99-00996-5
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.
P. L’Ecuyer and C. Lemieux, Variance Reduction via Lattice Rules, Management Science 46 (2000), no. 9, 1214–1235.
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.
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, DOI 10.1007/BF01457454
J. Leydold, H. Leeb, and W. Hörmann, Higher-Dimensional Properties of Non-Uniform Pseudo-Random Variates, In [H. Niederreiter and J. Spanier (eds.), Monte Carlo and Quasi-Monte Carlo Methods 1998, Springer, Berlin, 2000.
George Marsaglia, The structure of linear congruential sequences, Applications of number theory to numerical analysis (Proc. Sympos., Univ. Montréal, Montreal, Que., 1971) Academic Press, New York, 1972, pp. 249–285. MR 0411115
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, DOI 10.1137/1.9781611970081
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, DOI 10.1007/978-1-4612-1690-2
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, DOI 10.1007/978-1-4612-2552-2
H. Niederreiter and J. Spanier (eds.), Monte Carlo and Quasi-Monte Carlo Methods 1998, Springer, Berlin, 2000.
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.
Michael E. Pohst, Computational algebraic number theory, DMV Seminar, vol. 21, Birkhäuser Verlag, Basel, 1993. MR 1243639, DOI 10.1007/978-3-0348-8589-8
B. D. Ripley, The lattice structure of pseudorandom number generators, Proc. Roy. Soc. London Ser. A 389 (1983), no. 1796, 197–204. MR 719645
V. Shoup, NTL: A Library for doing Number Theory, http://www.shoup.net/.
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
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/.