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/Polynomial Sequences).

See also: LatSeq

Exhaustive Sequences

An exhaustive sequence of lattice definitions considers all the generating vectors in a Cartesian product of sequences of generator values. First, a vector of sequences of generating values must be initialized (see Vectors of Integer/Polynomial Sequences for details):

template <LatticeType LA>
void test(typename LatticeTraits<LA>::Modulus modulus){
   SizeParam<LA, EmbeddingType::UNILEVEL> size(modulus);      
   SizeParam<LA, EmbeddingType::UNILEVEL> size0(LatticeTraits<LA>::TrivialModulus);   
   Dimension dim = 3;
   typedef GenSeq::GeneratingValues<LA, 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);
   std::cout << latSeq << std::endl;
   
}

The class template LatSeq::Combiner produces a sequence of lattice definitions by associating a distinct sequence of generator values to each coordinate of the generating vector. It takes two template arguments: the first one is the type of individual sequence of generator values; the second one is a policy for combining the individual sequences, which corresponds to the Cartesian product of all sequences in this example. Then, the output is generated with:

test<LatticeType::ORDINARY>(8);

which produces:

[Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 1],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 3],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 5],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 7],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 3, 1],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 3, 3],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 3, 5],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 3, 7],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 5, 1],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 5, 3],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 5, 5],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 5, 7],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 7, 1],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 7, 3],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 7, 5],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 7, 7]]

while

test<LatticeType::POLYNOMIAL>(PolynomialFromInt(7));

produces:

[Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1
  1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1
  0 1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1
  1 1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  0 1
  1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  0 1
  0 1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  0 1
  1 1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1 1
  1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1 1
  0 1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1 1
  1 1]

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:

template <LatticeType LA>
void test(typename LatticeTraits<LA>::Modulus modulus){
   SizeParam<LA, EmbeddingType::UNILEVEL> size(modulus);      
   SizeParam<LA, EmbeddingType::UNILEVEL> size0(LatticeTraits<LA>::TrivialModulus);   
   Dimension dim = 3;
   size_t r = 4; // 4 random samples
   typedef GenSeq::GeneratingValues<LA, Compress::NONE, Traversal::Random<LFSR258>> 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);
   std::cout << latSeq << std::endl;
   
}

Thus, we can have independent values for each coordinate. The complete example can be found in tutorial/LatSeqRandom.cc and outputs:

[Ordinary Lattice - Modulus = 31 - Generating vector = [1, 20, 4],
 Ordinary Lattice - Modulus = 31 - Generating vector = [1, 14, 17],
 Ordinary Lattice - Modulus = 31 - Generating vector = [1, 21, 22],
 Ordinary Lattice - Modulus = 31 - Generating vector = [1, 23, 27]]
[Polynomial Lattice - Modulus = [1 1 1 1 1] - Generating vector = 
  1
  1 0 1
  0 0 1,
 Polynomial Lattice - Modulus = [1 1 1 1 1] - Generating vector = 
  1
  0 1 1 1
  0 1,
 Polynomial Lattice - Modulus = [1 1 1 1 1] - Generating vector = 
  1
  0 1 1
  1 1 1,
 Polynomial Lattice - Modulus = [1 1 1 1 1] - Generating vector = 
  1
  0 0 0 1
  0 0 1 1]

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 :

template<LatticeType LA>
void test(typename LatticeTraits<LA>::Modulus modulus){
   SizeParam<LA, EmbeddingType::UNILEVEL> size(modulus);
   Dimension dim = 3;
   typedef GenSeq::GeneratingValues<LA, Compress::NONE> Coprime;
   auto latSeq = LatSeq::korobov(size, Coprime(size), dim);
   std::cout << latSeq << std::endl;
}

test<LatticeType::ORDINARY>(7);

test<LatticeType::POLYNOMIAL>(PolynomialFromInt(7));

The output of the above code is:

[Ordinary Lattice - Modulus = 7 - Generating vector = [1, 1, 1],
 Ordinary Lattice - Modulus = 7 - Generating vector = [1, 2, 4],
 Ordinary Lattice - Modulus = 7 - Generating vector = [1, 3, 2],
 Ordinary Lattice - Modulus = 7 - Generating vector = [1, 4, 2],
 Ordinary Lattice - Modulus = 7 - Generating vector = [1, 5, 4],
 Ordinary Lattice - Modulus = 7 - Generating vector = [1, 6, 1]]
[Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1
  1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  0 1
  1 1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1 1
  0 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 with 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, genv);

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 :

template<LatticeType LA>
void test(typename LatticeTraits<LA>::Modulus modulus, typename LatticeTraits<LA>::GeneratingVector genv){
   SizeParam<LA, EmbeddingType::UNILEVEL> size(modulus);
   
   auto baseLat = createLatDef(size, genv);
   typedef GenSeq::GeneratingValues<LA, Compress::NONE> Coprime;
   auto latSeq = LatSeq::cbc(baseLat, Coprime(size));
   std::cout << latSeq << std::endl;
}

test<LatticeType::ORDINARY>(8, {1,5});

test<LatticeType::POLYNOMIAL>(PolynomialFromInt(7), {PolynomialFromInt(1),PolynomialFromInt(5)});

The output of the above code is:

[Ordinary Lattice - Modulus = 8 - Generating vector = [1, 5, 1],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 5, 3],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 5, 5],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 5, 7]]
[Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1 0 1
  1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1 0 1
  0 1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1 0 1
  1 1]

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: " << std::endl << baseLat << std::endl;
      std::cout << 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: " << std::endl << seq << std::endl;
   // select the first element
   return seq.begin();
}

This would output:

searching for the best lattice in dimension: 1
possible choices: 
[Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 3],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 5],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 7]]
selected lattice: 
Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1]


searching for the best lattice in dimension: 2
possible choices: 
[Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 1],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 3],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 5],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 7]]
selected lattice: 
Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 1]


searching for the best lattice in dimension: 3
possible choices: 
[Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 1, 1],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 1, 3],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 1, 5],
 Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 1, 7]]
selected lattice: 
Ordinary Lattice - Modulus = 8 - Generating vector = [1, 1, 1, 1]



searching for the best lattice in dimension: 1
possible choices: 
[Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  0 1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1 1]
selected lattice: 
Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1


searching for the best lattice in dimension: 2
possible choices: 
[Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1
  1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1
  0 1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1
  1 1]
selected lattice: 
Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1
  1


searching for the best lattice in dimension: 3
possible choices: 
[Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1
  1
  1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1
  1
  0 1,
 Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  1
  1
  1
  1 1]
selected lattice: 
Polynomial Lattice - Modulus = [1 1 1] - Generating vector = 
  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.