Iterating through a sequence of lattice definitions and evaluating a figure of merit for each element, as in Weighted Figures of Merit, is a common task when searching for good lattice parameters.

LatBuilder abstracts out this process by providing sequences of (computed) merit values.

See also: MeritSeq

CBC Construction

The example in tutorial/MeritSeqCBC.cc improves on the example from A Simple Example Using CBC Construction.

The base lattice and its merit value are managed by MeritSeq::CBC, so we can remove the declarations of baseLat and initialMerit, and introduce:

auto cbc = MeritSeq::cbc(storage, figure);

In the CBC loop, we instantiate the sequence of merit values with:

auto meritSeq = cbc.meritSeq(baseDim == 0 ? genSeq0 : genSeq);

Because the elements of meritSeq are of the abstract type MeritValue, we need to convert them to the Real type using an empty list of merit value filters declared as:

MeritFilterList<LA, L> filters;

and applied with:

auto filteredSeq = filters.apply(meritSeq);

Such a filter list can also be used to combine the merit values of individual levels in the case of embedded lattices (see Filters and Combiners). Then, we replace the minimization loop with a call to std::min_element:

auto best = std::min_element(filteredSeq.begin(), filteredSeq.end());

and notify the CBC instance that we have found our best lattice for the current dimension:

cbc.select(best.base());

Here, best is an iterator on the filteredSeq sequence, and best.base() is an iterator on corresponding element of the underlying meritSeq sequence. 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)
CBC search for dimension: 1
base lattice: 
Ordinary Lattice - Modulus = 256 - Generating vector = []
base merit value: 0
new projections: [{0}]
BEST LATTICE: 
Ordinary Lattice - Modulus = 256 - Generating vector = [1]
Merit value: 0.7
CBC search for dimension: 2
base lattice: 
Ordinary Lattice - Modulus = 256 - Generating vector = [1]
base merit value: 0.7
new projections: [{1}, {0,1}]
BEST LATTICE: 
Ordinary Lattice - Modulus = 256 - Generating vector = [1, 15]
Merit value: 0.7
CBC search for dimension: 3
base lattice: 
Ordinary Lattice - Modulus = 256 - Generating vector = [1, 15]
base merit value: 0.7
new projections: [{2}, {0,2}, {1,2}, {0,1,2}]
BEST LATTICE: 
Ordinary Lattice - Modulus = 256 - Generating vector = [1, 15, 39]
Merit value: 0.746627

CBC Construction Using Signals

To improve on the above example by using signals, we can reintroduce the Observer class from A Improved Example Using Signals. We also need to notify the Observer class when a new minimum value is updated, with a few changes:

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(); }
   bool onProgress(Real merit) const
   { return merit <= m_bestMerit; }
   void onAbort(const LatDef& lat) const
   { std::cout << "rejected:" << std::endl << lat; }
   void onMinUpdated(const Real& bestMerit)
   { m_bestMerit = bestMerit; }
private:
   Real m_bestMerit;
};

So, instead of using std::min_element, we use Functor::MinElement and connect its Functor::MinElement::onMinUpdated() signal to Observer::onMinUpdated():

Functor::MinElement<Real> minElement;

minElement.onMinUpdated().connect(boost::bind(&Observer<LA>::onMinUpdated, &obs, _1));

Then replace the call to std::min_element() with:

obs.reset();

auto best = minElement(filteredSeq.begin(), filteredSeq.end(), 0);

Also note the call to Observer::reset() to initialize the best observed merit value before using minElement. The resulting code can be found in tutorial/MeritSeqCBCSignals.cc .

CBC Construction for Coordinate-Uniform Figures of Merit

Figures of merit in a coordinate-uniform form can be evaluated more efficiently than the general weighted figures of merit. Here, we consider the case of the weighted \(\mathcal P_\alpha\) discrepancy for ordinary lattices, and the case of the weighted \(\mathcal P_{\alpha,PLR}\) for polynomial lattices. by adapting the code from CBC Construction . First, we replace the WeightedFigureOfMerit instance with an instance of CoordUniformFigureOfMerit: For ordinary lattices:

   auto weights = unique<LatticeTester::ProductWeights>();
   weights->setDefaultWeight(0.7);
   CoordUniformFigureOfMerit<Kernel::PAlpha> figure(std::move(weights), 2);
   std::cout << "figure of merit: " << figure << std::endl;

For polynomial lattices:

   auto weights = unique<LatticeTester::ProductWeights>();
   weights->setDefaultWeight(0.7);
   CoordUniformFigureOfMerit<Kernel::PAlphaPLR> figure(std::move(weights), 2);
   std::cout << "figure of merit: " << figure << std::endl;

The type of weights must be specified as a template argument because a different evaluation algorithm is used for different types of weights. Then, we replace the MeritSeq::CBC instance with a MeritSeq::CoordUniformCBC instance:

auto cbc = MeritSeq::cbc<MeritSeq::CoordUniformInnerProd>(storage, figure);

The MeritSeq::CoordUniformInnerProd template argument specifies that we want to use a standard inner product during CBC exploration. The complete example can be found in tutorial/MeritSeqCoordUniform.cc.

Fast CBC Construction

Here, we modify the example from CBC Construction for Coordinate-Uniform Figures of Merit in order to use the fast CBC method, which is implemented only with coordinate-uniform figures of merit. First, we need to replace MeritSeq::CoordUniformInnerProd with MeritSeq::CoordUniformInnerProdFast:

auto cbc = MeritSeq::cbc<MeritSeq::CoordUniformInnerProdFast>(storage, figure);

The fast CBC algorithm requires a special ordering of the generator values, so we also need to replace:

typedef GenSeq::GeneratingValues<LA, decltype(figure)::suggestedCompression()> Coprime;

with:

typedef GenSeq::CyclicGroup<LA, decltype(figure)::suggestedCompression()> Coprime;

Note that instantiating GenSeq::CyclicGroup requires the number of points to be an integer power of a prime base. Then, we modify the instantiation of meritSeq accordingly:

auto meritSeq = cbc.meritSeq(baseDim == 0 ? genSeq0 : genSeq);

The complete example can be found in tutorial/MeritSeqFastCBC.cc.

Non-CBC Construction Methods

In LatBuilder, sequences of merit values for non-CBC exploration methods are available only as a wrapper of the CBC exploration applied independently to each lattice definition, by replacing the sequences of candidate lattice definitions by singletons that contain only the candidate lattice being currently examined. CBC exploration can thus output only this one lattice, together with its merit value. This enables the efficient computation algorithms used in the coordinate-uniform case with standard CBC.

The example in tutorial/MeritSeqNonCBC.cc illustrates how to transform the CBC search from CBC Construction for Coordinate-Uniform Figures of Merit into a Korobov search. First, we create an instance of MeritSeq::LatSeqOverCBC and a sequence of Korobov lattice definitions:

auto latSeqOverCBC = MeritSeq::latSeqOverCBC(cbc);

auto latSeq = LatSeq::korobov(storage.sizeParam(), Coprime(storage.sizeParam().modulus()), dimension);

Then, the whole CBC loop is replaced with the execution of the Korobov search:

   auto meritSeq = latSeqOverCBC.meritSeq(latSeq);
   auto filteredSeq = filters.apply(meritSeq);
   auto best = std::min_element(filteredSeq.begin(), filteredSeq.end());
   std::cout << "BEST LATTICE: " << std::endl << *best.base().base() << "Merit value: " << *best << std::endl;