Lattice Builder Manual
Software Package for Constructing Rank-1 Lattices
|
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 :
The StorageType
traits class maps a LatType value to a type of storage through template specialization.
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:
Then, we instantiate a sequence of projections to which the figure of merit applies with:
We also allocate a storage instance for ordinary lattices with appropriate compression:
We define an observer which will keep track of the best candidate lattice:
Finally, we can iterate through all lattices and display the best observed candidate lattice:
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
:
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
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:
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:
Then, we connect the listener to the signals with:
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
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:
and to create a loop over its dimension:
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:
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:
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