This tutorial explains how to transform a sequence of merit values using filters, and how to combine the merit values of individual levels in the case of embedded lattices.

Normalization and Low-Pass

Here we build on the example from CBC Construction for Coordinate-Uniform Figures of Merit by normalizing the merit values and by applying a low-pass filter.

We add a normalizer to our MeritFilterList instance with:

   auto normalizer = unique<Norm::Normalizer<LA, L, Norm::PAlphaSL10>>(
         Norm::PAlphaSL10(figure.kernel().alpha(), figure.weights())
         );
   setLevelWeights(*normalizer, storage.sizeParam());
   filters.add(std::move(normalizer));

This Norm::Normalizer instance uses the bound on the \(\mathcal P_\alpha\) discrepancy derived in [31] implemented by Norm::PAlphaSL10. Then, we add a low-pass filter to reject candidate lattice with a normalized merit value larger than unity:

auto lowPass = unique<MeritFilter<LA, L>>(Functor::LowPass<Real>(1.0), "low-pass");

filters.add(std::move(lowPass));

Also note how we've changed the output instruction to:

std::cout << "BEST LATTICE: " << std::endl << cbc.baseLat() << "Merit value: " << *best << std::endl;

Here, best is an iterator on the sequence of filtered merit values filteredSeq, best.base() is an iterator on the unfiltered merit values meritSeq, and best.base().base() is an iterator on the underlying sequence of lattice definitions. Finally, we must create a Storage instance:

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

test(Storage<LatticeType::ORDINARY, EmbeddingType::MULTILEVEL, Compress::SYMMETRIC>(256), dim);

The complete code for this example can be found in tutorial/FilteredCBC.cc.

Filtered Random CBC

The example in tutorial/FilteredRCBC.cc shows how to implement random CBC construction with filtered merit values. We use the same normalization and low-pass filters as in Normalization and Low-Pass. We want to try samples independent random values for each component of the generating vector, excluding those that are rejected by the low-pass filter. This means that we don't know in advance the total number of values per coordinate to be tried. So, we first configure an infinite sequence of random integers:

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

auto genSeq = GenSeq::Creator<Coprime>::create(storage.sizeParam());

We also replace std::min_element with the Functor::MinElement functor:

Functor::MinElement<Real> minElement;

Next, we use signals to stop the search after samples random integers have passed through the low-pass filter:

   Observer<LA, L> obs(samples);
   minElement.onStart().connect(boost::bind(&Observer<LA, L>::onStart, &obs));
   minElement.onElementVisited().connect(boost::bind(&Observer<LA, L>::onElementVisited, &obs, _1));
   filters.template onReject<L>().connect(boost::bind(&Observer<LA, L>::onReject, &obs, _1));

The Functor::MinElement functor visits every element between the two iterators filteredSeq.begin() and filteredSeq.end() sequentially. The Functor::MinElement::onStart() signal is emitted, before it starts iterating through the elements. Every time a new element is visited, the Functor::MinElement::onElementVisited() signal is emitted; if a function connected to this signal returns false, the functor aborts its iteration and returns the minimum value observed so far. We use this feature to stop iterating through our infinite sequence of random integers. The MeritFilterList::onReject() signal is emitted whenever one of the filters rejects a candidate lattice (by returning false). The new Observer class is designed to keep track of the number of accepted candidate lattices and of the total number of candidate lattices tried, as:

template <LatticeType LA, EmbeddingType ET>
class Observer {
public:
   typedef LatBuilder::LatDef<LA, ET> LatDef;
   Observer(int maxCount) { m_maxCount = maxCount; m_count = m_totalCount = 0; }
   void onStart() { m_count = m_totalCount = 0; }
   bool onElementVisited(const Real&) { ++m_totalCount; return ++m_count < m_maxCount; }
   void onReject(const LatDef&) { m_count--; }
   int count() const { return m_count; }
   int totalCount() const { return m_totalCount; }
private:
   int m_maxCount;
   int m_count;
   int m_totalCount;
};

Note that Observer::onElementVisited() increases both the accepted count m_count and the total count m_totalCount, whereas Observer::onReject() decreases only m_count. Finally, we output the number of accepted and the total number candidate lattices:

std::cout << "BEST LATTICE: " << std::endl << cbc.baseLat() << "Merit value: " << *best << std::endl;

std::cout << obs.count() << " accepted / " << obs.totalCount() << " tried" << std::endl;;

The output of this example is:

figure of merit: Coordinate Uniform with Kernel: P2
Weights: ProductWeights([], default=0.7)
Norm type: 2
filters: Embedding type: Unilevel
Unilevel filters: normalizer: PAlphaSL10, low-pass
CBC search for dimension: 1
base lattice: 
Ordinary Lattice - Modulus = 257 - Generating vector = []
base merit value: 0
BEST LATTICE: 
Ordinary Lattice - Modulus = 257 - Generating vector = [1]
Merit value: 0.0105903
15 accepted / 15 tried
CBC search for dimension: 2
base lattice: 
Ordinary Lattice - Modulus = 257 - Generating vector = [1]
base merit value: 3.48667e-05
BEST LATTICE: 
Ordinary Lattice - Modulus = 257 - Generating vector = [1, 76]
Merit value: 0.0346885
15 accepted / 17 tried
CBC search for dimension: 3
base lattice: 
Ordinary Lattice - Modulus = 257 - Generating vector = [1, 76]
base merit value: 0.00125208
BEST LATTICE: 
Ordinary Lattice - Modulus = 257 - Generating vector = [1, 76, 96]
Merit value: 0.175129
15 accepted / 15 tried

Embedded Lattices and Combiners

Constructing embedded lattices requires combining the merit values associated to each nested level into a single compound merit value. The example in tutorial/FilteredCBC.cc shows how to do this by building on the example from Normalization and Low-Pass.

We need to change the scalar filters to filters that apply to the merit value of each individual level by replacing Real with RealVector:

   MeritFilterList<LA, L> filters;
   setCombiner(filters);
   auto normalizer = unique<Norm::Normalizer<LA, L, Norm::PAlphaSL10>>(
         Norm::PAlphaSL10(figure.kernel().alpha(), figure.weights())
         );
   setLevelWeights(*normalizer, storage.sizeParam());
   filters.add(std::move(normalizer));
   auto lowPass = unique<MeritFilter<LA, L>>(Functor::LowPass<Real>(1.0), "low-pass");
   filters.add(std::move(lowPass));
   std::cout << "filters: " << filters << std::endl;

Note that the normalizer needs per-level weights for multilevel figures of merit, which we all set to the inverse of the number of levels (power + 1) here:

   normalizer.setWeights(RealVector(
            sizeParam.maxLevel() + 1,
            1.0 / sizeParam.maxLevel()
            ));

Next, we configure the combiner as a sum of the normalized values across all levels:

template<LatticeType LA>
void setCombiner(MeritFilterList<LA, EmbeddingType::MULTILEVEL>& filters)
{ filters.add(unique<MeritCombiner::Accumulator<LA, Functor::Sum>>()); }

We also need change the storage type to Storage<EmbeddingType::MULTILEVEL>:

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

test(Storage<LatticeType::ORDINARY, EmbeddingType::MULTILEVEL, Compress::SYMMETRIC>(256), dim);

This example outputs:

figure of merit: Coordinate Uniform with Kernel: P2
Weights: ProductWeights([], default=0.7)
Norm type: 2
filters: Embedding type: Unilevel
Unilevel filters: normalizer: PAlphaSL10, low-pass
CBC search for dimension: 1
base lattice: 
Ordinary Lattice - Modulus = 256 - Generating vector = []
base merit value: 0
BEST LATTICE: 
Ordinary Lattice - Modulus = 256 - Generating vector = [1]
Merit value: 0.00379617
CBC search for dimension: 2
base lattice: 
Ordinary Lattice - Modulus = 256 - Generating vector = [1]
base merit value: 3.51396e-05
BEST LATTICE: 
Ordinary Lattice - Modulus = 256 - Generating vector = [1, 99]
Merit value: 0.0160699
CBC search for dimension: 3
base lattice: 
Ordinary Lattice - Modulus = 256 - Generating vector = [1, 99]
base merit value: 0.00123717
BEST LATTICE: 
Ordinary Lattice - Modulus = 256 - Generating vector = [1, 99, 27]
Merit value: 0.0874655
figure of merit: Coordinate Uniform with Kernel: P2
Weights: ProductWeights([], default=0.7)
Norm type: 2
filters: Embedding type: Multilevel
Combiner: Sum
Multilevel filters: normalizer: PAlphaSL10, low-pass
CBC search for dimension: 1
base lattice: 
Ordinary Lattice - Modulus = 2^8 - Generating vector = []
base merit value: [0, 0, 0, 0, 0, 0, 0, 0, 0]
BEST LATTICE: 
Ordinary Lattice - Modulus = 2^8 - Generating vector = [1]
Merit value: 0.0622623
CBC search for dimension: 2
base lattice: 
Ordinary Lattice - Modulus = 2^8 - Generating vector = [1]
base merit value: [2.30291, 0.575727, 0.143932, 0.0359829, 0.00899573, 0.00224893, 0.000562233, 0.000140558, 3.51396e-05]
BEST LATTICE: 
Ordinary Lattice - Modulus = 2^8 - Generating vector = [1, 45]
Merit value: 0.187022
CBC search for dimension: 3
base lattice: 
Ordinary Lattice - Modulus = 2^8 - Generating vector = [1, 45]
base merit value: [9.9092, 4.46607, 1.9866, 0.551031, 0.23438, 0.0762869, 0.0158076, 0.00575074, 0.00166391]
BEST LATTICE: 
Ordinary Lattice - Modulus = 2^8 - Generating vector = [1, 45, 69]
Merit value: 0.302157

Notice that the base merit value is now a vector of per-level merit values.