Lattice Builder Manual
Software Package for Constructing Rank1 Lattices

Search for a good generating vector involves enumerating the values its components can take.
The representation of search spaces in Lattice Builder is based on sequences of possible values for the components of the generating vector.
In the general case, one normally needs to enumerate all integers that are relatively prime with the number of points \(n\) in the lattice point set. This is implemented by the class template GenSeq::CoprimeIntegers. Some figures of merit are invariant under the transformation \(a \mapsto n  a\) where \(a\) is any component of the generating vector. When using such a symmetric figure of merit, redundancy can be avoided by enumerating only the first half of the sequence of integers coprime with \(n\), i.e. by compressing the search space. In that case, we pass Compress::Symmetric as the first template argument to GenSeq::CoprimeIntegers:
Otherwise, we pass Compress::None:
These concepts are illustrated in tutorial/GenSeqCoprimeIntegers.cc :
The ouput of the above code is:
lattice size: 7 whole sequence: [1, 2, 3, 4, 5, 6] half sequence: [1, 2, 3] lattice size: 8 whole sequence: [1, 3, 5, 7] half sequence: [1, 3] lattice size: 12 whole sequence: [1, 7, 5, 11] half sequence: [1, 5]
Sometimes, as with random Korobov or random CBC construction, it is necessary to randomly select a certain number of elements from a GenSeq::CoprimeIntegers instance. GenSeq::CoprimeIntegers optionally takes a second template arguments that specifies a method of traversal of its values; it defaults to Traversal::Forward which enumerates the values in their original order in the sequence. It can be replaced with Traversal::Random for the above purpose:
The traversal type Traversal::Random also takes a template argument that specifies the type of random generator to use. We use LFSR258 in our example, but any C++11compliant random engine could be used. Next, a random traversal object must be instantiated with the desired number r
of random samples:
Then, the sequence object can be instantiated with the lattice size n
, and the traversal object:
A complete example can be found in tutorial/GenSeqRandom.cc :
The output of the above code is:
lattice size: 31 (4 random samples) sequence: [3, 8, 6, 1] same sequence: [3, 8, 6, 1] other sequence: [15, 7, 13, 15] lattice size: 256 (4 random samples) sequence: [19, 63, 49, 5] same sequence: [19, 63, 49, 5] other sequence: [123, 59, 111, 119]
Note that GenSeq::Random stores its own copy of the random engine, so that successive iteration over the same random sequence objects yields the same sequence of values. To obtain a different random selection of values, the initial state of the random generator must be changed. The LFSR258 generator exposes a jump() function for this purpose:
In some situations, the number r
of random samples is not known in advance. In that case, the preferred method is to instantiate the traversal object without passing the argument r
, which defaults to infinity, then to add a stopping condition in loops that iterate over the elements of the sequence.
In the case where the lattice size \(n\) is an integer power of a prime base, the class template GenSeq::CyclicGroup can be used to enumerate the elements of the cyclic group of integers modulo \(n\) can be enumerated, in the natural group order where the \(i\)th element is \(g^i \bmod n\), where \(g\) is the group generator. This is useful in particular to perform fast CBC construction. Like GenSeq::CoprimeIntegers, GenSeq::CyclicGroup takes a compression type as the first template argument. This is illustrated in tutorial/GenSeqCyclicGroup.cc :
The output of the above code is:
lattice size: 7^1 whole sequence: [1, 3, 2, 6, 4, 5] half sequence: [1, 3, 2] lattice size: 2^3 whole sequence: [1, 5, 7, 3] half sequence: [1, 3] lattice size: 3^2 whole sequence: [1, 2, 4, 8, 7, 5] half sequence: [1, 2, 4]
In the symmetric case, each value \(a\) is mapped to \(\min\{a, na\}\).
Construction algorithms often consider a distinct sequence of possible values for each component of the generating vector. When distinct random selection of sequence elements are required for each coordinate, as with random CBC or plain random constructions; in this case, the initial state of the random generator must be different for each coordinate, as explained in Random Traversal. This functionality is provided by the convenience template class GenSeq::VectorCreator, which automatically calls jump() on the random generator between different coordinates if the traversal method is Traversal::Random.
A vector of dim
sequences of type Seq
with size parameter n
can be created with:
In most situations when constructing rank1 lattices, we consider only the value 1 for the first component. For that purpose, we can replace the first integer sequence with a singleton that contains only the value 1 with:
A full example can be found in tutorial/GenSeqVector.cc :
The output of the above code is:
lattice size: 7 integer sequences: [[1], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]]
For random sequence types, the number of random samples can be passed as an additional optional argument to GenSeq::VectorCreator::create():
The output of the above code is:
lattice size: 31 random integer sequences: [[1], [29, 14, 26, 29, 9], [28, 18, 29, 28, 12]]
Distinct random sequences are automatically created.
A lattice with \(b^m\) points in dimension \(s\) and generating vector \(\boldsymbol a = (a_1,\dots,a_s)\) can be extended to \(b^{m+1}\) points by appending a \(m+1\)st digit in base \(b\) to the left of each \(a_j\). It is easy to verify that the original lattice is indeed embedded in the extended lattice. The following instruction shows how to instantiate a sequence of generator values seq
that adds a \(m+1\)st digit in base b
, where numPoints = b
\(^m\) to the left of the \(m\) digits in base b
of the integer gen
(which stands for any of the \(a_j\)'s):
In practice, low
would be one of the \(a_j\)'s. To add two digits instead of one, the first constructor argument b * numPoints
must be replaced with b * b * numPoints
. A complete example can be found in tutorial/GenSeqExtend.cc.