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.