Lattice Builder Manual
Software Package for Constructing Rank-1 Lattices
|
Search spaces consist of sequences of lattice definitions, which can be constructed based on a size parameter and on sequences of generator values (as in Vectors of Integer Sequences).
An exhaustive sequence of lattice definitions considers all the generating vectors in a Cartesian product of integer sequences. First, a vector of integer sequences must be initialized (see Vectors of Integer Sequences for details):
Next, the sequence of lattice is initialized using the size parameter and the vector of integer sequences:
The class template LatSeq::Combiner produces a sequence of lattice definitions by associating a distinct integer sequence to each coordinate of the generating vector. It takes two template arguments: the first one is the type of individual integer sequence; the second one is a policy for combining the individual sequences, which corresponds to the Cartesian product of all integer sequences in this example. Then, the output is generated with:
which produces:
[lattice(8, [1, 1, 1]), lattice(8, [1, 1, 3]), lattice(8, [1, 1, 5]), lattice(8, [1, 1, 7]), lattice(8, [1, 3, 1]), lattice(8, [1, 3, 3]), lattice(8, [1, 3, 5]), lattice(8, [1, 3, 7]), lattice(8, [1, 5, 1]), lattice(8, [1, 5, 3]), lattice(8, [1, 5, 5]), lattice(8, [1, 5, 7]), lattice(8, [1, 7, 1]), lattice(8, [1, 7, 3]), lattice(8, [1, 7, 5]), lattice(8, [1, 7, 7])]
The complete example can be found in tutorial/LatSeqExhaustive.cc.
To produce a sequence of lattice definitions with random generating vectors, we adapt the example from Exhaustive Sequences by assigning a random traversal type to the integer sequences:
In Exhaustive Sequences, we used the CartesianProduct policy for combining the input sequences. Here, we use Zip, which generates a sequence such that the \(i\)-th output value is a vector whose \(j\)-th component consist of the \(i\)-th value of the \(j\)-th input sequence:
Thus, we can have independent values for each coordinate. The complete example can be found in tutorial/LatSeqRandom.cc and outputs:
[lattice(31, [1, 29, 28]), lattice(31, [1, 14, 18]), lattice(31, [1, 26, 29]), lattice(31, [1, 29, 28])]
For sequences of Korobov lattices, a single sequence of generator values is required, as all components of the generating vector depend on the second one. A sequence of Korobov lattice definitions can be created with:
A complete example can be found in tutorial/LatSeqKorobov.cc :
The output of the above code is:
[lattice(7, [1, 1, 1]), lattice(7, [1, 2, 4]), lattice(7, [1, 3, 2]), lattice(7, [1, 4, 2]), lattice(7, [1, 5, 4]), lattice(7, [1, 6, 1])]
The component-by-component construction method consists in selecting the generating vector one coordinate at a time. To select the \(j\)-th, we consider a sequence of lattice definitions when the same first \(j-1\) coordinates. In the following example, we set \(j=3\) with the first two coordinates equal to 1 and 5, respectively. First, we instantiate what we call a base lattice:
Next, we create the sequence of lattice definitions resulting from appending to the base lattice each value from an integer sequence of type Coprime:
The full example can be found in tutorial/LatSeqCBC1.cc :
The output of the above code is:
[lattice(8, [1, 5, 1]), lattice(8, [1, 5, 3]), lattice(8, [1, 5, 5]), lattice(8, [1, 5, 7])]
In a practical situation, we would probably loop over \(j\) to construct the generating vector. Building over the above example, the following loop illustrates this idea:
The findBest()
function is assumed to take a sequence of candidate lattice definitions for input and returns and iterator on the ``best'' lattice definition. Then, bestLat
is updated with the value pointed to by the iterator. For example, the definition of findBest()
could be one that selects the first lattice definition of the sequence:
This would output:
searching for the best lattice in dimension: 1 possible choices: [lattice(8, [1, 1]), lattice(8, [1, 3]), lattice(8, [1, 5]), lattice(8, [1, 7])] selected lattice: lattice(8, [1, 1]) searching for the best lattice in dimension: 2 possible choices: [lattice(8, [1, 1, 1]), lattice(8, [1, 1, 3]), lattice(8, [1, 1, 5]), lattice(8, [1, 1, 7])] selected lattice: lattice(8, [1, 1, 1]) searching for the best lattice in dimension: 3 possible choices: [lattice(8, [1, 1, 1, 1]), lattice(8, [1, 1, 1, 3]), lattice(8, [1, 1, 1, 5]), lattice(8, [1, 1, 1, 7])] selected lattice: lattice(8, [1, 1, 1, 1])
A more useful definition of findBest()
would rather compute the merit values of each candidate lattice and select the optimal one. The current example, however, illustrates the basic ideas and can be found in tutorial/LatSeqCBC.cc.