Home
SpectralTest Home
LLLSpectral Test
CSource
MathSource
Maintained by
Karl.Entacher@fhsbg.ac.at

Spectral Test Server
LLL  Version
The sections below shows how to perform efficient
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 vector in a lattice.
Instead of the shortest vector we discuss an application of 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.
For an implementation of the LLLspectral test in C choose the
menue item C  Source.
Spectral Test Approximation with the LLLAlgorithm
Table of Contents:
Application and Analysis of Lattices for Monte Carlo  and
Quasi Monte Carlo Methods
Monte Carlo (MC)
Classical node sets for Monte Carlo (MC) methods are obtained by linear
congruential random number generators (LCGs).
LCGs have extensively been applied for a long time and they are
the most common random number generators. Although we have to
mention that recent versions use implementations based on a combination of
LCGs, or multiple recursive generators (MRGs)
to get improved quality and huge periods.
For many classical and recent examples, see [8,16].
The definitions and basic properties of linear random number generators
are contained in [11,14,15,22].
LCGs are generated by means of the recursion
, ,
and by an initial seed , , ,
(the least residue system modulo ).
Normalized PRNs in are obtained by the transformation .
We consider only multiplicative where the modulus is prime LCGs ()
and the multiplier is a primitive
root modulo . Therefore the recursion above, with seed ,
produces a sequence of integers in with maximal period .
A central property of linear congruential generators in general
(this holds also for combined LCGs and for MRGs), is that
arbitrary dimensional vectors

(1) 
with fixed lags , , ,
are contained in certain grid structures [18].
For , , , the case which has been studied
in detail, these vectors are called overlapping tuples.
In our case, for multiplicative LCGs, the latter tuples
produce intersections of a lattice
with the dimensional unit cube , where

(2) 
denotes a dimensional lattice with lattice basis

(3) 
see [11,14,15,21,22,24].
In practice usually nonoverlapping tuples

(4) 
are used to produce ``independent'' random points in .
If
, hence the dimension does not divide the period
of the generator, then all possible nonoverlapping tuples
originate in the same lattice as above. Note that for the computation of
all nonoverlapping tuples with an LCG one has to generate at least
times the period.
If
, these vectors produce true subsets of the lattice
which must not have a pure lattice structure in
general [1]. A lattice is obtained if one considers the union
of all possible subsets produced by such tuples.
Essentially different lattices are obtained for
vectors (1) with arbitrary lags which
occur if, for example, lagged subsequences from the output
of an LCG are used [9,18].
QuasiMonte Carlo (QMC)
MC  and also QMC methods can efficiently be applied
for an approximate calculation of high dimensional integrals.
Consider the standard domain in dimension , a point
(node) set
in ,
,
and a function
.
The (quasi) Monte Carlo approximation of an integral
is computed by the average of
the integrand over the point set

(5) 
A classical method for quasi Monte Carlo integration uses the
intersection of the full lattice , ,
with the dimensional unit cube as node set for the calculation
of the latter approximation.
Note that the difference of MC and QMC integration in our case
lies in the fact that
for MC one may use a large modulus and only a ``random'' part of the
lattice , and for QMC, one may apply the sample size as
modulus and therefore the full lattice .
The application of is called rank1 lattice rule or
Korobov lattice rule [13,19,22,26]. The quality
of depends on the generating vector in (3).
For well chosen vectors , the Korobov lattice rule is also called
method of ``good lattice points'' (GLPs).
More general lattice rules are for example obtained for
different vectors in basis (3).
Lattice Assessment
The coarseness of the lattice may
change dramatically if either the dimension or the multiplier
are varied. To get reliable linear random number generators for a large
class of applications, it is necessary to assess
the quality of the several lattices produced by various tuple constructions
described above. Furthermore, the selection of ``good'' lattices
provides excellent QMC node sets as well.
The spectral test (geometric version) is a classical measure for the
quality of dimensional lattices .
Specifically, this test determines the maximum distance between
adjacent hyperplanes, taken over all families of parallel hyperplanes
which contain all points of the lattice. The smaller the more regular
is the point structure.
Widely used is a normalized spectral test
, ,
for which
(values near 1 imply a good lattice structure).
The constants are absolute lower bounds on , see
[14, p. 105] and [11, Sect. 7.7].
L'Ecuyer [17] used also certain lower bounds for
dimensions in order to compute for arbitrary dimensions.
The algorithm to calculate the spectral test is based on the
dual lattice of ,
since the maximal distance of adjacent hyperplanes
is equal to one over the length of the shortest vector of the dual lattice
[6,14]. Historically this test is due to
Coveyou and MacPherson [5] who used multivariate Fourier analysis
to study the quality of LCGs.
An efficient implementation of the spectral test for arbitrary
multiple recursive generators is given in [18].
Spectral Test Approximation with the LLL Algorithm
In this section we want to demonstrate the effects which appear if
the shortest vector in the spectral test calculation
is replaced by an approximation obtained by the Lenstra Lenstra Lovász (LLL)
basis reduction algorithm [4,20,23].
The calculation of the shortest vectors in a lattice is performed by
variants of the FinckePohst algorithm which are in general not
polynomial in dimension [10].
Applying the LLL algorithm, an approximation of the shortest vector
can be calculated in polynomial time [4,23,27].
For recent discussions on the complexity of lattice problems see
[2,3], and also other papers from [7].
For a given basis
of a lattice ,
the LLL algorithm finds a new basis
,
with

(6) 
where denotes the shortest vector in ,
the euclidian norm,
and an arbitrary nonzero vector in the lattice .
Therefore the latter inequality also holds for a shortest vector
in .
Further properties of LLL reduced bases are given in the book of
Cohen [4]. The latter author quotes:
``We see that the vector in a reduced basis is,
in a very precise sense,
not too far from being the shortest nonzero vector of .
In fact, it often is the shortest, and when it is not, one can, most of
the time, work with instead of the actual shortest vector''.
Moreover, Pohst [23] supplements: ``Examples
show that there exist lattices with LLL reduced bases
with
.
These observations certainly do not favour applications of LLL reduced
bases. However, the results in practice are in general much better than
the worst case estimates.''
In the following we demonstrate that the above statements on the good
behavior in practice apply also for the spectral test for parameter
selection of MC and QMC node sets.
Therefore, in most cases, it is sufficient to apply the LLL reduction
instead of the calculation of the shortest vector.
Consider our lattices , prime,
as defined in Section 1.
The LLL spectral test of will obviously be defined as one
over the length of the first vector of the LLL reduced dual
lattice basis of .
Similar as in Subsection 1.3 we may also use
a normalized LLL spectral test
, .
Further we will use the notation
which in
the original form
has often been applied
for LCG parameter searches [11,17]. For fixed prime numbers
we will write , and for the
corresponding figures of merit for lattice .
To exhibit different behavior of the spectral test and its LLL version
for our lattices we considered the nearest prime numbers to
,
which are for example
and, for each of these primes, the set of primitive
roots modulo . Note that assessments of lattices
for MC node set selection are in general restricted to the set of all
primitive roots modulo since for such primitve roots
the corresponding LCG guarantees maximal period.
There are primitive roots where
denotes the Euler totient function. Further there are certain
lattices for which are equivalent with respect to the
spectral test and therefore
it suffices to assess for a number of
primitive roots [11,17].
Figure 1 shows relative frequences of the occurrence of different
values of and (left graphics) and
and , (right graphics).
For prime numbers , we considered all relevant primitive
roots modulo , and for with
,
we have randomly chosen a set of primitive roots .
The relative number of different values and ,
is very low (maximum about three percent)
but increasing with the dimension.
However for the measures
and the frequences are significantly lower.
We have chosen since the normalization
constants used for the normalized spectral test are best possible for
dimensions , which is not the case for larger dimensions
[17].
In Figure 2 we exhibit the magnitude of the differences of
the measures.
The left graphics shows the maximal values
for each prime number ,
and dimension .
Note that almost all values are between one and two.
There are some outliers, the largest one equals 7 which for dimension is
still clearly lower than the theoritical
bound given in (6).
For dimension all values are equal to one which means that in all
cases in dimension two the LLL reduction already provided the shortest vector
i.e. . The latter property can also be seen from the right
graphics in Figure 1 and 2.
The right graphics shows the mean values of the absolute differences between
and .
Figure 1:
Relative frequences of the occurrence of different
values of and (left graphics) and
and , (right graphics).

Figure 2:
The maximal values for
each prime number ,
and dimension
(left graphics) and
the mean values of the absolute differences of and
(right graphics).

From these empirical tests we can confirm the statements of
Cohen and Pohst above,
i.e. for our applications the vector of the LLL reduced
dual basis of is very often the shortest vector and if not the
results are much better than the theoretical bounds.
Our comparisons have been calculated using a Mathematica implementation
of the FinckePohst algorithm by Wilberd van der Kallen,
University of Utrecht NL,
which is based on a previous LLL reduction.
Figure 3 exhibits the time performance of our calculations.
The figure displays the mean values of the time used for
the calculation of divided by the means for , the
means are taken over 64 different primitive roots for each prime .
The LLL reduction is for small dimensions about a factor 5 faster than the
calculation of the shortest vector, but the speedup in our Mathematica
implementation decreases for increasing dimension and prime size.
Figure 3:
Mean values of the time spent for
divided by the means for , the
means taken over 64 different primitive roots for each prime .

We further used Victor Shoup's C++ implementation of the LLL algorithm
[25] and performed the same parameter searches for optimal multipliers
with respect to which were carried out
in [17, Table 2]. For the exhaustive searches in the latter paper
which were computed for prime numbers
we got exactly the same
multipliers with respect to and equal values for the measures
and . For the random searches for primes
, for example,
we easily obtained improved results with our algorithm. Table 1
shows the results given in [17, Table 2] and our multipliers
selected with LLL for the latter primes.
 1

L. Afflerbach.
The sublattice structure of linear congruential random number
generators.
Manuscripta Mathematica, 55:455465, 1986.
 2

J Ajtai.
Generating Hard Instances of Lattice Problems.
Report TR96007, Electronic Colloquium on Computational Complexity
ECCC, 1996.
Webpage: [7].
 3

J Cai.
Some Recent Progress on the Complexity of Lattice Problems.
Report TR99006, Electronic Colloquium on Computational Complexity
ECCC, 1999.
Webpage: [7].
 4

H. Cohen.
A Course in Computational Algebraic Number Theory,
volume 138 of Graduate Texts in Mathematics.
SpringerVerlag, 1993.
 5

R.R. Coveyou and R.D. MacPherson.
Fourier analysis of uniform random number generators.
J. Assoc. Comput. Mach., 14:100119, 1967.
 6

U. Dieter.
How to Calculate Shortest Vectors in a Lattice.
Math. Comp., 29(131):827833, 1975.
 7

ECCC.
Electronic Colloquium on Computational Complexity ECCC.
http://www.eccc.unitrier.de/eccc/.
 8

K. Entacher.
A collection of selected pseudorandom number generators with linear
structures  advanced version.
Technical report, Dept. of Mathematics, University Salzburg, Austria,
available at: http://random.mat.sbg.ac.at/ , 1998.
The previous version is published as technical report 971,
ACPCAustrian Center for Parallel Computation, University of Vienna,
Austria, 1997.
 9

K. Entacher.
Parallel Streams of Linear Random Numbers in the Spectral
Test.
ACM Transactions on Modeling and Computer Simulation, 9(1):3144, 1999.
 10

U. Fincke and M. Pohst.
Improved methods for calculating vectors of short length in a
lattice, including a complexity analysis.
Math. Comp., 44:463471, 1985.
 11

G.S. Fishman.
Monte Carlo: Concepts, Algorithms, and Applications,
volume 1 of Springer Series in Operations Research.
Springer, New York, 1996.
 12

P. Hellekalek and G. Larcher (eds.).
Random and QuasiRandom Point Sets, volume 138 of Lecture Notes in Statistics.
Springer, Berlin, 1998.
 13

F.J. Hickernell.
Lattice Rules: How Well Do They Measure Up.
In [12] pp 109166.
 14

D.E. Knuth.
The Art of Computer Programming, volume 2: Seminumerical
Algorithms.
AddisonWesley, Reading, MA, 2nd edition, 1981.
 15

P. L'Ecuyer.
Uniform random number generation.
Ann. Oper. Res., 53:77120, 1994.
 16

P. L'Ecuyer.
Random Number Generation.
In Jerry Banks, editor, Handbook of Simulation, Chapter
4. Wiley, 1998.
 17

P. L'Ecuyer.
Tables of Linear Congruential Generators of Different
Sizes and Good Lattice Structure.
Mathematics of Computation, 68(225):249260, 1999.
 18

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(2):209217, 1997.
 19

P. L'Ecuyer and C. Lemieux.
Variance Reduction via Lattice Rules.
Management Science, to appear, 2000.
 20

A.K. Lenstra, H.W. Lenstra, and L. Lovász.
Factoring polynomials with rational coefficients.
Mathematische Annalen, 261:515534, 1982.
 21

G. Marsaglia.
The structure of linear congruential sequences.
In S. K. Zaremba, editor, Applications of Number Theory to
Numerical Analysis, pages 248285. Academic Press, New York, 1972.
 22

H. Niederreiter.
Random Number Generation and QuasiMonte Carlo Methods.
SIAM, Philadelphia, 1992.
 23

M.E. Pohst.
Computational Algebraic Number Theory.
DMV Seminar Band 21. Birkhäuser Verlag, 1993.
 24

B.D. Ripley.
The lattice structure of pseudorandom number generators.
Proc. Roy. Soc. London Ser. A, 389:197204, 1983.
 25

V. Shoup.
NTL: A Library for doing Number Theory.
http://www.shoup.net/.
 26

I.H. Sloan and S. Joe.
Lattice Methods for Multiple Integration.
Oxford Univ. Press, New York, 1994.
 27

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/.
