Lattice Builder Manual Software Package for Constructing Rank-1 Lattices

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Modules Pages
Filters and Combiners

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<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 [18] 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<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: " << cbc.baseLat() << " with 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<LatType::ORDINARY, Compress::SYMMETRIC>(256), dim);
test(Storage<LatType::EMBEDDED, 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::CoprimeIntegers<decltype(figure)::suggestedCompression(), Traversal::Random<LFSR113>> 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<L> obs(samples);
minElement.onStart().connect(boost::bind(&Observer<L>::onStart, &obs));
minElement.onElementVisited().connect(boost::bind(&Observer<L>::onElementVisited, &obs, _1));
filters.template onReject<L>().connect(boost::bind(&Observer<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 <LatType LAT>
class Observer {
public:
typedef LatBuilder::LatDef<LAT> 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: " << cbc.baseLat() << " with merit value " << *best << std::endl;
std::cout << " " << obs.count() << " accepted / " << obs.totalCount() << " tried" << std::endl;;

The output of this example is:

    BEST LATTICE: lattice(257, [1]) with merit value 0.0105903
      15 accepted / 15 tried
    BEST LATTICE: lattice(257, [1, 116]) with merit value 0.0401108
      15 accepted / 17 tried
    BEST LATTICE: lattice(257, [1, 116, 19]) with merit value 0.205199
      15 accepted / 19 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<L> filters;
setCombiner(filters);
auto normalizer = unique<Norm::Normalizer<L, Norm::PAlphaSL10>>(
Norm::PAlphaSL10(figure.kernel().alpha(), figure.weights())
);
setLevelWeights(*normalizer, storage.sizeParam());
filters.add(std::move(normalizer));
auto lowPass = unique<MeritFilter<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:

void setCombiner(MeritFilterList<LatType::EMBEDDED>& filters)
{ filters.add(unique<MeritCombiner::Accumulator<Functor::Sum>>()); }

We also need change the storage type to Storage<LatType::EMBEDDED>:

test(Storage<LatType::ORDINARY, Compress::SYMMETRIC>(256), dim);
test(Storage<LatType::EMBEDDED, Compress::SYMMETRIC>(256), dim);

This example outputs:

    figure of merit: CoordUniformFigureOfMerit(kernel=P2, weights=ProductWeights([], default=0.7))
    filters: multilevel filters=(normalizer, low-pass), combiner=sum, scalar filters=()
    CBC search for dimension: 1
      base lattice: lattice(2^8, [])
      base merit value: [0, 0, 0, 0, 0, 0, 0, 0, 0]
    BEST LATTICE: lattice(2^8, [1]) with merit value 0.0622623
    CBC search for dimension: 2
      base lattice: lattice(2^8, [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: lattice(2^8, [1, 45]) with merit value 0.187022
    CBC search for dimension: 3
      base lattice: lattice(2^8, [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: lattice(2^8, [1, 45, 69]) with merit value 0.302157

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