Lattice Builder Manual Software Package for Constructing Rank-1 Lattices

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Modules Pages
Sequences of Lattice Definitions

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

See also
  LatSeq

# Exhaustive 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):

SizeParam<LatType::ORDINARY> size(8);
SizeParam<LatType::ORDINARY> size0(2);
Dimension dim = 3;
typedef GenSeq::CoprimeIntegers<Compress::NONE> Coprime;
auto genSeqs = GenSeq::VectorCreator<Coprime>::create(size, dim);
// consider only 1 for 1st coordinate
genSeqs[0] = GenSeq::Creator<Coprime>::create(size0);

Next, the sequence of lattice is initialized using the size parameter and the vector of integer sequences:

auto latSeq = LatSeq::combine<CartesianProduct>(size, genSeqs);

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:

std::cout << latSeq << std::endl;

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.

# Random Sequences

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:

SizeParam<LatType::ORDINARY> size(31);
SizeParam<LatType::ORDINARY> size0(2);
Dimension dim = 3;
size_t r = 4; // 4 random samples
typedef GenSeq::CoprimeIntegers<Compress::NONE, Traversal::Random<LFSR113>> Coprime;
auto genSeqs = GenSeq::VectorCreator<Coprime>::create(size, dim, r);
// consider only 1 for 1st coordinate
genSeqs[0] = GenSeq::Creator<Coprime>::create(size0);

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:

auto latSeq = LatSeq::combine<Zip>(size, genSeqs);

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])]

# Korobov Sequences

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:

auto latSeq = LatSeq::korobov(size, Coprime(size), dim);

A complete example can be found in tutorial/LatSeqKorobov.cc :

SizeParam<LatType::ORDINARY> size(7);
Dimension dim = 3;
typedef GenSeq::CoprimeIntegers<Compress::NONE> Coprime;
auto latSeq = LatSeq::korobov(size, Coprime(size), dim);
std::cout << latSeq << std::endl;

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])]

# Component-by-Component Sequences

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:

auto baseLat = createLatDef(size, GeneratingVector{1, 5});

Next, we create the sequence of lattice definitions resulting from appending to the base lattice each value from an integer sequence of type `Coprime:`

auto latSeq = LatSeq::cbc(baseLat, Coprime(size));

The full example can be found in tutorial/LatSeqCBC1.cc :

SizeParam<LatType::ORDINARY> size(8);
auto baseLat = createLatDef(size, GeneratingVector{1, 5});
typedef GenSeq::CoprimeIntegers<Compress::NONE> Coprime;
auto latSeq = LatSeq::cbc(baseLat, Coprime(size));
std::cout << latSeq << std::endl;

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:

while (baseLat.dimension() < dim) {
auto latSeq = LatSeq::cbc(baseLat, Coprime(size));
auto itBest = findBest(latSeq);
baseLat = *itBest;
std::cout << " selected lattice: " << baseLat << std::endl;
}

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:

// search for the best lattice in the sequence
template <typename SEQ>
typename SEQ::const_iterator findBest(const SEQ& seq)
{
std::cout << "searching for the best lattice in dimension: " << seq.baseLat().dimension() << std::endl;
std::cout << " possible choices: " << seq << std::endl;
// select the first element
return seq.begin();
}

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.