TY - JOUR
T1 - Efficient lattice assessment for LCG and GLP parameter searches
AU - Entacher, K.
AU - Schell, T.
AU - Uhl, A.
N1 - Cited By :7
Export Date: 14 December 2023
Correspondence Address: Entacher, K.; Sch. of Telecommunications Eng., Schillerstr 30, A-5020 Salzburg, Austria; email: [email protected]
References: Afflerbach, L., The sub-lattice structure of linear congruential random number generators (1986) Manuscripta Mathematica, 55, pp. 455-465. , MR 87k:65006; Ajtai, J., Generating hard instances of lattice problems (1996) Electronic Colloquium on Computational Complexity ECCC, , Report TR96-007, Web-page: [9]; Caflisch, R.E., Monte Carlo and Quasi-Monte Carlo methods (1998) Acta Numer., 7, pp. 1-49. , MR 2000e:65019; Cai, J., Some recent progress on the complexity of lattice problems (1999) Electronic Colloquium on Computational Complexity ECCC, , Report TR99-006, Web-page: [9]; Coddington, P., Random number generators for Parallel Computers (1996) NHSE Review, Second Issue, , http://nhse.cs.rice.edu/NHSEreview/RNG/, Northeast Parallel Architectures Center; Cohen, H., A course in computational algebraic number theory (1993) Graduate Texts in Mathematics, 138. , Springer-Verlag, MR 94i:11105; Coveyou, R.R., Macpherson, R.D., Fourier analysis of uniform random number generators (1967) J. Assoc. Comput. Mach., 14, pp. 100-119. , MR 36:4779; Dieter, U., How to calculate shortest vectors in a lattice (1975) Math. Comp., 29 (131), pp. 827-833. , MR 52:291; Electronic Colloquium on Computational Complexity ECCC, , http://www.eccc.uai-trier.de/eccc/; Entacher, K., (1997) A collection of selected pseudorandorn number generators with linear structures - advanced version, , http://www.fh-sbg.ac.at/~entacher, Tech. report, Dept. of Mathematics, University Salzburg, Austria, 1998, The previous version is published as technical report 97-1, ACPC-Austrian Center for Parallel Computation, University of Vienna, Austria; Parallel streams of linear random numbers in the spectral test (1999) ACM Transactions on Modeling and Computer Simulation, 9 (1), pp. 31-44; Entacher, K., Hellekalek, P., L'Ecuyer, P., Quasi-Monte Carlo node sets from linear congruential generators (2000) Monte Carlo and Quasi-Monte Carlo Methods 1998, pp. 188-198. , H. Niederreiter and J. Spanier, eds., Springer; Entacher, K., Uhl, A., Wegenkittl, S., Linear congruential generators for Parallel Monte-Carlo: The leap-frog case (1998) Monte Carlo Methods and Appl., 4 (1), pp. 1-16. , CMP 98:12; Fincke, U., Pohst, M., Improved methods for calculating vectors of short length in a lattice, including a complexity analysis (1985) Math. Comp., 44, pp. 463-471. , MR 86e:11050; Fishman, G.S., Monte Carlo: Concepts, algorithms, and applications (1996) Springer Series in Operations Research, 1. , Springer, New York, MR 97g:65019; Hellekalek, P., Don't trust Parallel Monte Carlo (1998) Twelfth Workshop on Parallel and Distributed Simultation PAD'98, pp. 82-89. , May 26th - 29th (Banff, Alberta, Canada), IEEE Computer Society, Los Alamitos, California; Hellekalek, P., Larcher, G., Random and quasi-random point sets (1998) Lecture Notes in Statistics, 138. , Springer, Berlin. MR 99g:11003; Hickernell, F.J., Lattice Rules: How Well Do They Measure Up?, pp. 109-166. , 17, MR 2000b:65007; Knuth, D.E., (1981) The art of computer programming, 2nd ed., vol. 2: Seminumerical Algorithms, 2. , Addison-Wesley, Reading, MA, MR 83i:68003; L'Ecuyer, P., Uniform random number generation (1994) Ann. Oper. Res., 53, pp. 77-120. , MR 95k:65007; Bad lattice structures for vectors of non-successive values produced by some linear recurrences (1997) INFORMS Journal on Computing, 9, pp. 57-60. , MR 98f:65014; Banks, J., Random number generation (1998) Handbook of Simulation, , Chapter 4, Wiley; Tables of linear congruential generators of different sizes and good lattice structure (1999) Mathematics of Computation, 68 (225), pp. 249-260. , MR 99c:11101; L'Ecuyer, P., Couture, R., An implementation of the lattice and spectral tests for multiple recursive linear random number generators (1997) INFORMS Journal on Computing, 9 (2), pp. 209-217. , CMP 98:03; L'Ecuyer, P., Lemieux, C., Variance reduction via lattice rules (2000) Management Science, 46 (9), pp. 1214-1235; Lemieux, C., L'Ecuyer, P., On selection criteria for lattice rules and other Quasi-Monte Carlo point sets (2001) Mathematics and Computers in Simulation, 55, pp. 139-148. , CMP 2001:11; Lenstra, A.K., Lenstra, H.W., Lovász, L., Factoring polynomials with rational coefficients (1982) Mathematische Annalen, 261, pp. 515-534. , MR 84a:12002; Leydold, J., Leeb, H., Hörmann, W., Higher-Dimensional Properties of Non-Uniform Pseudo-Random Variates, pp. 341-355. , 33; Marsaglia, G., The structure of linear congruential sequences (1972) Applications of Number Theory to Numerical Analysis, pp. 248-285. , S. K. Zaremba, ed., Academic Press, New York. MR 53:14854; Niederreiter, H., (1992) Random number generation and quasi-Monte Carlo methods, , SIAM, Philadelphia, MR 93h:65008; Niederreiter, H., Hellekalek, P., Larcher, G., Zinterhof, P., Monte Carlo and Quasi-Monte Carlo methods 1996 (1998) Lecture Notes in Statistics, 127. , Springer, New York, MR 99d:65005; Niederreiter, H., Shiue, P.J.-S., Monte Carlo and Quasi-Monte Carlo methods in scientific computing (1995) Lecture Notes in Statistics, 106. , Springer, New York, MR 97j:65002; Niederreiter, H., Spanier, J., (2000) Monte Carlo and Quasi-Monte Carlo Methods 1998, , Springer, Berlin; Owen, A.B., Monte Carlo extension of Quasi-Monte Carlo (1998) Proceedings of the 1998 Winter Simulation Conference, pp. 571-577. , http://www.informs-cs.org/, D.J. Madeiros, E.F. Watson, J.S. Carson, and M.S. Manivannan, eds; Pohst, M.E., Computational algebraic number theory (1993) DMV Seminar Band, 21. , Birkhäuser Verlag, MR 94j:11132; Ripley, B.D., The lattice structure of pseudo-random number generators (1983) Proc. Roy. Soc. London Set. A, 389, pp. 197-204. , MR 85i:65010; Shoup, V., NTL: A Library for doing Number Theory, , http://www.shoup.net/; Sloan, I.H., Joe, S., (1994) Lattice methods for multiple integration, , Oxford Univ. Press, New York, MR 98a:65026; Storjohann, A., (1996) Faster Algorithms for Integer Lattice Basis Reduction, , http://www.inf.ethz.ch/research/wr/, Technical report, Institute of Scientific Computing, ETH Zürich
PY - 2002
Y1 - 2002
N2 - 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.
AB - 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.
KW - Fincke-Pohst algorithm
KW - Good lattice points
KW - Lattice basis reduction
KW - Lattice rules
KW - LLL algorithm
KW - Monte Carlo and quasi-Monte Carlo methods
KW - Random number generation
KW - Spectral test
U2 - 10.1090/S0025-5718-01-01415-6
DO - 10.1090/S0025-5718-01-01415-6
M3 - Article
SN - 0025-5718
VL - 71
SP - 1231
EP - 1242
JO - Mathematics of Computation
JF - Mathematics of Computation
IS - 239
ER -