Lattice Builder Manual Software Package for Constructing Rank-1 Lattices
Weighted Figures of Merit

# Storage

In Lattice Builder, the algorithms that evaluate figures of merit all store and operate on some data internally, whose representation may vary depending on the type of lattice and of figure of merit under consideration.

First, evaluating a figure of merit for ordinary 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)$$ of the kernel $$\omega$$ for $$i=0,\dots,n-1$$ are precomputed and stored in a vector for subsequent use. For ordinary lattices, the elements of the vector are stored in a natural order (see Storage<LatType::ORDINARY>), by increasing value of $$i$$. For embedded lattices in bas $$b$$, the internal representation of the vector is different (see Storage<LatType::EMBEDDED>): 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 can be found in the first $$b^k$$ 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, 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 Lattice Builder is specified by a Storage instance. These classes perform time-critical operations (such as permutation) and for that reason are not polymorphic.

Consider the following example from tutorial/Storage.cc :

template <LatType LAT, Compress COMP>
void test(Modulus n)
{
SizeParam<LAT> size(n);
Storage<LAT, 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()
{
Modulus n = 16;
test<LatType::ORDINARY, Compress::NONE>(n);
test<LatType::EMBEDDED, Compress::NONE>(n);
test<LatType::ORDINARY, Compress::SYMMETRIC>(n);
test<LatType::EMBEDDED, Compress::SYMMETRIC>(n);
return 0;
}

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

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<LatCommon::ProductWeights>();
weights->setDefaultWeight(0.7);
typedef ProjDepMerit::Spectral<LatCommon::NormaBestLat> 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:

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 ordinary lattices with appropriate compression:

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

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

class Observer {
public:
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 << "\t:\t" << 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 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: " << obs.bestLat() << " with 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: WeightedFigureOfMerit(accumulator=max, projDepMerit=spectral^1 (symmetric), weights=ProductWeights([], default=0.7))
projections: [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]
lattice(19, [1, 1, 1])  :       1.6229 <-- best
lattice(19, [1, 2, 4])  :       1.02641 <-- best
lattice(19, [1, 3, 9])  :       1.02641
lattice(19, [1, 4, 16]) :       0.725784 <-- best
lattice(19, [1, 5, 6])  :       0.725784
lattice(19, [1, 6, 17]) :       1.02641
lattice(19, [1, 7, 11]) :       0.7 <-- best
lattice(19, [1, 8, 7])  :       0.7
lattice(19, [1, 9, 5])  :       1.02641
BEST LATTICE: lattice(19, [1, 7, 11]) with merit value 0.7

Remarks
A weighted $$\mathcal P_\alpha$$ discrepancy could be obtained by replacing:
typedef ProjDepMerit::Spectral<LatCommon::NormaBestLat> ProjDep;
WeightedFigureOfMerit<ProjDep, Functor::Max> figure(2, std::move(weights));
with:
typedef ProjDepMerit::CoordUniform<Kernel::PAlpha> ProjDep;
WeightedFigureOfMerit<ProjDep, Functor::Sum> figure(std::move(weights), ProjDep(2));
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 " << lat << std::endl; }

Then, we connect the listener to the signals with:

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

With these changes, the output becomes:

figure of merit: WeightedFigureOfMerit(accumulator=max, projDepMerit=spectral^1 (symmetric), weights=ProductWeights([], default=0.7))
projections: [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]
lattice(19, [1, 1, 1])  :       1.6229 <-- best
lattice(19, [1, 2, 4])  :       1.02641 <-- best
lattice(19, [1, 3, 9])  :       1.02641
lattice(19, [1, 4, 16]) :       0.725784 <-- best
lattice(19, [1, 5, 6])  :       0.725784
rejected lattice(19, [1, 6, 17])
lattice(19, [1, 6, 17]) :       inf
lattice(19, [1, 7, 11]) :       0.7 <-- best
lattice(19, [1, 8, 7])  :       0.7
rejected lattice(19, [1, 9, 5])
lattice(19, [1, 9, 5])  :       inf
BEST LATTICE: lattice(19, [1, 7, 11]) with merit value 0.7


# 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 ? 2 : storage.sizeParam().numPoints())
);

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
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: WeightedFigureOfMerit(accumulator=max, projDepMerit=spectral^1 (symmetric), weights=ProductWeights([], default=0.7))
CBC search for dimension: 1
base lattice: lattice(19, [])
base merit value: 0
new projections: [{1}]
lattice(19, [1])        :       0.7 <-- best
BEST LATTICE: lattice(19, [1]) with merit value 0.7
CBC search for dimension: 2
base lattice: lattice(19, [1])
base merit value: 0.7
new projections: [{2}, {1,2}]
lattice(19, [1, 1])     :       1.6229 <-- best
lattice(19, [1, 2])     :       1.02641 <-- best
lattice(19, [1, 3])     :       0.725784 <-- best
lattice(19, [1, 4])     :       0.7 <-- best
lattice(19, [1, 5])     :       0.7
lattice(19, [1, 6])     :       0.725784
lattice(19, [1, 7])     :       0.7
lattice(19, [1, 8])     :       0.7
lattice(19, [1, 9])     :       1.02641
BEST LATTICE: lattice(19, [1, 4]) with merit value 0.7
CBC search for dimension: 3
base lattice: lattice(19, [1, 4])
base merit value: 0.7
new projections: [{3}, {1,3}, {2,3}, {1,2,3}]
lattice(19, [1, 4, 1])  :       1.6229 <-- best
lattice(19, [1, 4, 2])  :       1.02641 <-- best
lattice(19, [1, 4, 3])  :       0.725784 <-- best
lattice(19, [1, 4, 4])  :       1.6229
lattice(19, [1, 4, 5])  :       0.725784
lattice(19, [1, 4, 6])  :       0.725784
lattice(19, [1, 4, 7])  :       0.725784
lattice(19, [1, 4, 8])  :       1.02641
lattice(19, [1, 4, 9])  :       1.02641
BEST LATTICE: lattice(19, [1, 4, 3]) with merit value 0.725784