Storage

In LatBuilder, the algorithms that evaluate figures of merit all store and operate on some data internally, whose representation may vary depending on the lattice (ordinary/polynomial), the type of lattice (simple/embedded) and of figure of merit under consideration.

First, evaluating a figure of merit for simple or for embedded lattices imposes different requirement on internal data. For example, to evaluate a coordinate-uniform figure of merit, the values \(\omega(i/n)\) (respectively \(\omega(\nu_m(i(z)/P(z)))\) of the kernel \(\omega\) for \(i=0,\dots,n-1\) ( \(n = 2^{\deg(P(z))}\) for polynomial lattices) are precomputed and stored in a vector for subsequent use. For simple lattices, the elements of the vector are stored in a natural order (see Storage<LatticeType, EmbeddingType::UNILEVEL>), by increasing value of \(i\). For embedded lattices in basis \(b \in \mathbb{N}\) (respectively \(b \in \mathbb{Z}_2[z]) \), the internal representation of the vector is different (see Storage<LatticeType, EmbeddingType::MULTILEVEL>): it uses a permutation such that, for \(k=0,\dots,m\) where the highest-level lattice has \(n=b^m\), the values necessary to describe the level with \(b^k\) points (respectively \(2^{k \deg(b)}\) points) can be found in the first \(b^k\) elements (respectively \(2^{k \deg(b)}\) elements) stored in the permuted vector. This allows for adding the next higher level simply by extending this vector. It also simplifies performing vector operations on all different levels without having to process each level individually.

Second, in the case of ordinary lattices, the type of compression used also affects the internal representation of vectors. In the case of symmetric figures of merit, i.e. figures of merit that are invariant under the transformation \(a_j \mapsto n - a_j\) where \(a_j\) is any component of the generating vector, it is a waste of space and effort to represent every value internally. Considering the same example as above, only half of the values of \(\omega(i/n)\) need to be stored.

Finally, the size parameter of the lattice directly affects the length of the internal data vector.

To account for these three different aspects, the internal representation of vectors in LatBuilder is specified by a Storage instance. These classes perform time-critical operations (such as permutation) and for that reason are not polymorphic.

A detailed description can be found in Storage.

Consider the following example from tutorial/Storage.cc :

template <LatticeType LA, EmbeddingType ET, Compress COMP>
void test(typename LatticeTraits<LA>::Modulus modulus)
{
   SizeParam<LA, ET> size(modulus);
   Storage<LA, ET, COMP> storage(size);
   std::cout << "storage name: " << storage.name() << std::endl;
   std::cout << "  size parameter: " << storage.sizeParam() << std::endl;
   std::cout << "  virtual size:   " << storage.virtualSize() << std::endl;
   std::cout << "  actual size:    " << storage.size() << std::endl;
}
int main()
{
   SET_PATH_TO_LATNETBUILDER_FOR_EXAMPLES();
   uInteger n = 16;
   Polynomial P = PolynomialFromInt(7);
   test<LatticeType::ORDINARY, EmbeddingType::UNILEVEL, Compress::NONE>(n);
   test<LatticeType::ORDINARY, EmbeddingType::MULTILEVEL, Compress::NONE>(n);
   test<LatticeType::ORDINARY, EmbeddingType::UNILEVEL, Compress::SYMMETRIC>(n);
   test<LatticeType::ORDINARY, EmbeddingType::MULTILEVEL, Compress::SYMMETRIC>(n);
   test<LatticeType::POLYNOMIAL, EmbeddingType::UNILEVEL, Compress::NONE>(P);
   test<LatticeType::POLYNOMIAL, EmbeddingType::MULTILEVEL, Compress::NONE>(P);
   return 0;
}

The StorageType traits class maps a EmbeddingType value to a type of storage through template specialization.

See also: Storage

A Simple Example

The example from tutorial/WeightedFigureOfMerit.cc illustrates how to instantiate a weighted figure of merit and perform a search for the best Korobov lattice. First we instantiate the sequence latSeq of lattice definitions roughly as in the example from Korobov Sequences . Next, we instantiate a weighted spectral figure of merit, using a sum as its accumulator, and product weights:

   auto weights = unique<LatticeTester::ProductWeights>();
   weights->setDefaultWeight(0.7);
   typedef ProjDepMerit::Spectral<LatticeTester::NormaBestLat<Real>> ProjDep;
   WeightedFigureOfMerit<ProjDep, Functor::Max> figure(2, std::move(weights));
   std::cout << "figure of merit: " << figure << std::endl;

Then, we instantiate a sequence of projections to which the figure of merit applies with:

   LatticeTester::CoordinateSets::FromRanges allProjections(
         1, latSeq.latDimension(),     // range for dimension
         0, latSeq.latDimension() - 1  // range for coordinate index
         );
   std::cout << "projections: " << allProjections << std::endl;

We also allocate a storage instance for simple lattices with appropriate compression:

test(Storage<LatticeType::ORDINARY, EmbeddingType::UNILEVEL, Compress::SYMMETRIC>(19), dim);

We define an observer which will keep track of the best candidate lattice:

template<LatticeType LA>
class Observer {
public:
   typedef LatBuilder::LatDef<LA, EmbeddingType::UNILEVEL> LatDef;
   Observer() { reset(); }
   // initializes the best observed merit value to infinity
   void reset() { m_bestMerit = std::numeric_limits<Real>::infinity(); }
   // returns the best observed lattice
   const LatDef& bestLat() { return m_bestLat; }
   // returns the best observed merit value
   const Real bestMerit() { return m_bestMerit; }
   // notifies the observer that the merit value of a new candidate lattice has
   // been observed; updates the best observed candidate lattice if necessary
   void observe(const LatDef& lat, Real merit)
   {
      std::cout << lat;
      std::cout << "Merit: " << merit;
      if (merit < m_bestMerit) {
         std::cout << " <-- best";
         m_bestMerit = merit;
         m_bestLat = lat;
      }
      std::cout << std::endl;
   }
private:
   LatDef m_bestLat;
   Real m_bestMerit;
};

Finally, we can iterate through all lattices and display the best observed candidate lattice:

   auto eval = figure.evaluator(storage);
   Observer<LA> obs;
   for (const auto& lat : latSeq) {
      // compute merit value of lattice for all projections
      auto merit = eval(lat, allProjections, initialMerit);
      // notify the observer
      obs.observe(lat, merit);
   }
   std::cout << "BEST LATTICE: " << std::endl << obs.bestLat() << "Merit value: " << obs.bestMerit() << std::endl;

The purpose of the initialMerit object is to store the value of the figure of merit for projections other than that for which it is currently being evaluated (all projections, here). Thus, it is possible to split the evaluation of the figure of merit over different sets of coordinates. It is particularly useful in the case of component-by-component construction, where it can be used to store the merit value of the base lattice (before a component is appended to the generating vector). Here, it simply contains the value 0.0:

auto initialMerit = storage.createMeritValue(0.0);

The output of this example is:

figure of merit: Projection Dependent Merit: spectral^1 (symmetric) - Accumulator: Max
Norm Type: 2
Weights: ProductWeights([], default=0.7)
projections: [{0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}]
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 1, 1]
Merit: 5.37513 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 2, 4]
Merit: 2.15005 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 3, 9]
Merit: 2.15005
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 16]
Merit: 1.07503 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 5, 6]
Merit: 1.07503
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 6, 17]
Merit: 2.15005
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 7, 11]
Merit: 1.0257 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 8, 7]
Merit: 1.0257
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 9, 5]
Merit: 2.15005
BEST LATTICE: 
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 7, 11]
Merit value: 1.0257

Remarks: A weighted \(\mathcal P_\alpha\) discrepancy could be obtained by replacing:
typedef ProjDepMerit::Spectral<LatticeTester::NormaBestLat<Real>> ProjDep;
WeightedFigureOfMerit<ProjDep, Functor::Max> figure(2, std::move(weights));
with:
typedef ProjDepMerit::CoordUniform<Kernel::PAlpha> ProjDep;
WeightedFigureOfMerit<ProjDep, Functor::Sum> figure(2, std::move(weights), ProjDep(2));

The same applies for polynomial lattices. For example, we can look for the best Korobov lattice with respect to \(\mathcal P_{\alpha}\): we define the weighted figure of merit as follows:

typedef ProjDepMerit::CoordUniform<Kernel::PAlphaPLR> ProjDep;

WeightedFigureOfMerit<ProjDep, Functor::Sum> figure(2, std::move(weights), ProjDep(2));

We then execute

test(Storage<LatticeType::POLYNOMIAL, EmbeddingType::UNILEVEL, Compress::NONE>(PolynomialFromInt(13)), dim);

which gives the output:

figure of merit: Projection Dependent Merit: P2_PLR - Accumulator: Sum
Norm Type: 2
Weights: ProductWeights([], default=0.7)
projections: [{0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}]
Polynomial Lattice - Modulus = [1 0 1 1] - Generating vector = 
  1
  1
  1
Merit: 2.18057 <-- best
Polynomial Lattice - Modulus = [1 0 1 1] - Generating vector = 
  1
  0 1
  0 0 1
Merit: 1.0617 <-- best
Polynomial Lattice - Modulus = [1 0 1 1] - Generating vector = 
  1
  1 1
  1 0 1
Merit: 1.04103 <-- best
Polynomial Lattice - Modulus = [1 0 1 1] - Generating vector = 
  1
  0 0 1
  1 1 1
Merit: 1.04103
Polynomial Lattice - Modulus = [1 0 1 1] - Generating vector = 
  1
  1 0 1
  0 1 1
Merit: 1.02036 <-- best
Polynomial Lattice - Modulus = [1 0 1 1] - Generating vector = 
  1
  0 1 1
  1 1
Merit: 1.0617
Polynomial Lattice - Modulus = [1 0 1 1] - Generating vector = 
  1
  1 1 1
  0 1
Merit: 1.02036

See also: WeightedFigureOfMerit ProjDepMerit

A Improved Example Using Signals

The evaluation of the figure of merit by WeightedFigureOfMerit is performed by evaluating term-by-term a sum over a set of projections of a lattice. If, during the progress of evaluating the sum, the value partial sum becomes larger than the smallest merit value of other candidate lattices already evaluated, then there is no need to finish evaluating the sum. The same reasoning holds for a maximum instead of a sum too. The example in tutorial/WeightedFigureOfMeritSignals.cc shows how the evaluation process can be aborted using signals.

After contributing every new term into the sum (or maximum), WeightedFigureOfMerit emits the WeightedFigureOfMerit::onProgress() signal, passing the current cumulated value as its argument. This signal can be connected to any function (a signal listener) which takes for argument a constant reference to a MeritValue instance. If the signal listener returns true, WeightedFigureOfMerit continues the evaluation of the figure of merit; otherwise, it is aborted and the figure of merit evaluates to infinity. For example, we define:

bool onProgress(Real merit) const

{ return merit < m_bestMerit; }

in the Observer class. We also define a listener for WeightedFigureOfMerit::onAbort() which is emitted by WeightedFigureOfMerit upon abortion and which passes the rejected candidate lattice as its argument:

void onAbort(const LatDef& lat) const

{ std::cout << "rejected:" << std::endl << lat; }

Then, we connect the listener to the signals with:

   Observer<LA> obs;
   eval.onProgress().connect(boost::bind(&Observer<LA>::onProgress, &obs, _1));
   eval.onAbort().connect(boost::bind(&Observer<LA>::onAbort, &obs, _1));

With these changes, the output becomes:

figure of merit: Projection Dependent Merit: spectral^1 (symmetric) - Accumulator: Max
Norm Type: 2
Weights: ProductWeights([], default=0.7)
projections: [{0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2}]
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 1, 1]
Merit: 5.37513 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 2, 4]
Merit: 2.15005 <-- best
rejected:
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 3, 9]
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 3, 9]
Merit: inf
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 16]
Merit: 1.07503 <-- best
rejected:
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 5, 6]
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 5, 6]
Merit: inf
rejected:
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 6, 17]
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 6, 17]
Merit: inf
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 7, 11]
Merit: 1.0257 <-- best
rejected:
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 8, 7]
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 8, 7]
Merit: inf
rejected:
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 9, 5]
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 9, 5]
Merit: inf
BEST LATTICE: 
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 7, 11]
Merit value: 1.0257

A Simple Example Using CBC Construction

We can modify the example from A Simple Example to implement CBC construction as illustrated in Component-by-Component Sequences. The complete example can be found in tutorial/WeightedFigureOfMeritCBC.cc. The first step is to declare a base lattice:

auto baseLat = createLatDef(storage.sizeParam());

and to create a loop over its dimension:

   while (baseLat.dimension() < dimension) {
      Dimension baseDim = baseLat.dimension();
      auto latSeq = LatSeq::cbc(
            baseLat,
            Coprime(baseDim == 0 ? LatticeTraits<LA>::TrivialModulus : storage.sizeParam().modulus())
            );

where we instantiate a new lattice sequence every time the dimension of the base lattice is increased. When the dimension of the base lattice is zero, we need only consider 1 as a candidate value for the first component of the generating vector, whence the condition on baseDim above. Instead of covering all projections, we need only consider the projections that include the new coordinate in the generating vector:

      // base projections
      FromRanges baseProjections{
            0, baseDim,     // range for dimension
            0, baseDim - 1  // range for coordinate index
            };
      // add current coordinate to the base projections
      AddCoordinate<FromRanges> newProjections(
            baseProjections,
            baseDim         // current coordinate index
            );

The minimization loop is unchanged, except that allProjections is replace with newProjections. Finally, baseLat and initialMerit must be updated based on the best observed candidate lattice:

baseLat = obs.bestLat();

initialMerit = obs.bestMerit();

After these changes, the output becomes:

figure of merit: Projection Dependent Merit: spectral^1 (symmetric) - Accumulator: Max
Norm Type: 2
Weights: ProductWeights([], default=0.7)
CBC search for dimension: 1
base lattice: 
Ordinary Lattice - Modulus = 19 - Generating vector = []
base merit value: 0
new projections: [{0}]
Ordinary Lattice - Modulus = 19 - Generating vector = [1]
Merit: 0.7 <-- best
BEST LATTICE: 
Ordinary Lattice - Modulus = 19 - Generating vector = [1]
Merit value: 0.7
CBC search for dimension: 2
base lattice: 
Ordinary Lattice - Modulus = 19 - Generating vector = [1]
base merit value: 0.7
new projections: [{1}, {0,1}]
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 1]
Merit: 5.37513 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 2]
Merit: 2.15005 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 3]
Merit: 1.07503 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4]
Merit: 0.7 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 5]
Merit: 0.7
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 6]
Merit: 1.07503
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 7]
Merit: 0.826943
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 8]
Merit: 0.826943
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 9]
Merit: 2.15005
BEST LATTICE: 
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4]
Merit value: 0.7
CBC search for dimension: 3
base lattice: 
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4]
base merit value: 0.7
new projections: [{2}, {0,2}, {1,2}, {0,1,2}]
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 1]
Merit: 5.37513 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 2]
Merit: 2.15005 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 3]
Merit: 1.07503 <-- best
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 4]
Merit: 5.37513
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 5]
Merit: 1.07503
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 6]
Merit: 1.07503
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 7]
Merit: 1.07503
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 8]
Merit: 2.15005
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 9]
Merit: 2.15005
BEST LATTICE: 
Ordinary Lattice - Modulus = 19 - Generating vector = [1, 4, 3]
Merit value: 1.07503