Lattice Builder Manual
Software Package for Constructing Rank1 Lattices

This tutorial teaches how to use the Lattice Builder commandline tool to search for good rank1 lattices.
It is assumed in the examples that the latbuilder
executable program can be found by the user's shell. If it is not the case, the full path to the executable program, for example /path/to/latbuilder
, should be used in the place of just latbuilder
.
Alternatively, the Lattice Builder Web Application can be used to construct a command line, to invoke the commandline tool and to see the results.
This tutorial is divided into the following sections:
The following typesetting semantics is adopted:
verbatim
for text to be typed as is;arg
for text to be substituted;In this section, we start with a basic example to perform a standard componentbycomponent (CBC) construction, which we use to introduce the different commandline options. After, we extend that example in various ways to show how to achieve different specific tasks.
Consider the following basic example:
latbuilder \ latticetype ordinary \ size 2053 \ dimension 5 \ construction CBC \ figureofmerit CU:P2 \ weights product:0.7
The order in which the arguments are specified is not important. Some arguments consists of several tokens, separated by a colon.
latticetype ordinary
indicates that we seek an ordinary (in contrast to embedded) rank1 lattice rule. The construction of embedded lattices is illustrated in Embedded Lattices.size 2053
indicates that we seek a lattice rule with 2053 points.dimension 5
specifies that we seek a lattice point set of dimension 5.construction CBC
specifies that a CBC construction should be used. Specifying other construction methods is explained in Construction Type.figureofmerit CU:P2
consists of three colonseparated tokens. It tells Lattice Builder to use the specialized coordinateuniform evaluation algorithm, whence the first CU
token, for the \(\mathcal P_2\) discrepancy.weights product:0.7
assigns product weights to the figure of merit, with the same weight (0.7) for every coordinate. More general examples on how to specify the weights are given below in Specifying the Weights.To summarize, this command executes a CBC construction for an ordinary lattice with 2053 points in 5 dimensions, using the weighted \(\mathcal P_2\) figure of merit with an \(\ell_2\) norm, in coordinateuniform with product weights such that \(\gamma_j^2 = 0.7\) for all \(j\).
Option names come in long and short forms. For example, the following has the same effect as the previous example:
latbuilder l ordinary n 2053 d 5 c CBC m CU:P2 w product:0.7
The long forms are favored in this tutorial to make the examples selfexplanatory. For the sake of conciseness, in the derived examples, we only show the commandline parameters that need to be changed, or added; other parameters should be left as in the basic example.
This section covers the following topics:
With projectiondependent weights, the weight associated to the projection onto the coordinates in \(\mathfrak u\) can be set to any nonnegative constant \(\gamma_{\mathfrak u}\).
The projectiondependent weights cannot be specified directly on the command line. They have to be written to a text file, say weights.txt
, with a content similar to the following:
# this is a comment 1,2,3: 0.7 1,2,4: 0.5 2,3,4: 0.3 order 2: 1.0 order 3: 0.1 default: 1.0e3
This assigns the square weights 0.7, 0.5 and 0.3 to projections \(\{1,2,3\}\), \(\{1,2,4\}\) and \(\{2,3,4\}\), respectively, a square weight of 1.0 to every projection of order 2, a square weight of 0.1 to every projection of order 3 other than the above three for which weights were explicitly assigned, then a square weight of \(10^{3}\) to every other projection. The order of the lines in the file is not important. Lattice Builder must be told where to look for the weights by changing the weights argument to
weights file:weights.txt
The first colonseparated token indicates the type (projectiondependent) of weights, and the second one, the name of the file from which the weights must be read.
Note that the weights in the above examples are interpreted as square weights because, by default, the numerical values read by Lattice Builder are interpreted as the constants \(\gamma_{\mathfrak u}^p\), i.e. the weights elevated the power \(p\) matching the choice of \(\mathcal L_p\)norm. An exception to this occurs when using the infinitynorm, where they are interpreted as if \(p = 1\). To interpret the numerical values as another power of the weights, say 1, the option
weightspower 1
must be added to the command line.
With orderdependent weights, the weight associated to the projection onto the coordinates in \(\mathfrak u\) is
\[ \gamma_{\mathfrak u} = \Gamma_{\mathfrak u}. \]
In that case, the argument of the weights
option consists of three colonseparated tokens: the first is the type of weights (orderdependent weights); the second is the default weight assigned to projection orders for which no weight is explicitly given; the last token is optional and is a commaseparated list of orderdependent weights \(\Gamma_1,\dots,\Gamma_j\) for some \(j\).
weights orderdependent:0.3
weights orderdependent:0.1:1.0,0.7,0.3
With product weights, the weight associated to the projection onto the coordinates in \(\mathfrak u\) is
\[ \gamma_{\mathfrak u} = \prod_{j \in \mathfrak u} \gamma_j. \]
In that case, the argument of the weights
option consists of three colonseparated tokens: the first is the type of weights (product weights); the second is the default weight assigned to coordinates for which no weight is explicitly given; the last token is optional and is a commaseparated list of coordinate weights \(\gamma_1,\dots,\gamma_j\) for some \(j\).
weights product:0.3
weights product:0.1:1.0,0.7,0.3
With product and orderdependent (POD) weights, the weight associated to the projection onto the coordinates in \(\mathfrak u\) is
\[ \gamma_{\mathfrak u} = \Gamma_{\mathfrak u} \prod_{j \in \mathfrak u} \gamma_j. \]
In that case, the argument of the weights
option consists of five colonseparated tokens: the first is the type of weights (POD), the next two specify the \(\Gamma_j\)'s as in OrderDependent Weights, and the last two specify the \(\gamma_j\)'s as in Product Weights.
weights POD:0.1:1.0,0.7,0.3:0.5:1.0,0.9,0.7
\[ \max_{\emptyset \neq \mathfrak u \subseteq \{1,\dots,s\}} \gamma_{\mathfrak u} \left[ \bar{\mathcal L}_{\mathfrak u}(n, \boldsymbol a) \right] \]
where \(s\) is the dimension (5 in the basic example), \(n\) is the number of points (2053 in the basic example), \(\boldsymbol a\) is the generating vector (to be found), the constants \(\gamma_{\mathfrak u}\) are projectiondependent weights (specified as product weights in the basic example), and \(\bar{\mathcal L}_{\mathfrak u}(n, \boldsymbol a)\) is normalized maximum distance between two successive parallel hyperplanes:normtype inf figureofmerit spectral
\[ \sum_{\emptyset \neq \mathfrak u \subseteq \{1,\dots,s\}} \left[ \gamma_{\mathfrak u} \bar{\mathcal L}_{\mathfrak u}(n, \boldsymbol a) \right]^2 \]
figureofmerit spectralThe optional third colonseparated token specifies the exponent applied to the square brackets. It defaults to 1, as in the previous example.
figureofmerit P2 normtype 1.5
figureofmerit P4
figureofmerit CU:P4
figureofmerit CU:R1
figureofmerit CU:P2 filters norm:P2SL10Usage of the
filters
option is illustrated in Filtering Merit Values.Filters are optional and can be used to transform the computed values of a figure of merit, or to reject bad values. Multiple filters can be chained together by specifying multiple filter arguments separated by whitespace.
filters norm:P2SL10The first colonseparated token (
norm
) indicates that we want to apply a normalization. The second one is the type of normalization (here, a particular bound on \(\mathcal P_2\).filters norm:P2DPW08
filters norm:P2SL10 lowpass:1.0The first filter is explained above. The second filter consists of two colonseparated tokens: the first one (
lowpass
) indicates that we want to apply a lowpass filter on merit values; the second one specifies the threshold value of this lowpass filter.For usage with embedded lattices, see Embedded Lattices.
construction explicit:1,468,896,603,367
construction exhaustive
construction random:1000
construction random:1000 filters norm:P2SL10 lowpass:1.0
construction Korobov
construction randomKorobov:30
construction CBC
construction randomCBC:10
construction randomCBC:10 filter norm:P2SL10 lowpass:1.0
construction fastCBC
Constructing embedded lattices involves producing a compound merit value that accounts for the merit of each nested level. This compound merit value is computed as follows:
latticetype embedded
latbuilder \ latticetype embedded \ size "2^16" \ dimension 5 \ construction CBC \ figureofmerit spectral \ weights product:1.0 \ combiner maxThe size of the lattice with the largest number of points can be specified with the
size b^m
, as above with \(b=2\) and \(m=16\), or simply with size 65536
, where \(65,536 = 2^{16}\). The spectral merit is evaluated for each nested level, and the maximum value across all level is selected as the compound merit value, as specified with the argument combiner max
.latbuilder \ latticetype embedded \ size "2^16" \ dimension 10 \ construction fastCBC \ figureofmerit CU:P2 \ multilevelfilters norm:P2DPW08:even:8,16 lowpass:1.0 \ weights product:0.1 \ combiner sumThe
multilevelfilters
argument specifies filters that must be applied individually to each embedded level. The first filter is a normalization using the weighted bound on the \(\mathcal P_2\) figure of merit as derived in [5] , with even weights across all levels from \(m=8,\dots,16\), and no weight for other levels. If regular filters were also specified with the filters
argument, they would apply to the combined merit value. Here the argument combiner sum
indicates that the normalized merit values should be added to produce the combined merit value.If no combiner is explicitly specified, Lattice Builder defaults to selecting the merit value of the maximum level (highest value of \(m\)), which is equivalent to constructing ordinary lattices. This combiner can also be explicitly selected with:
combiner level:max
It is also possible to select any given level, say \(m=8\), with
combiner level:8
Suppose you have constructed embedded lattice rules up to $2^8$ points in dimension 5 with:
latbuilder \ latticetype embedded \ size "2^8" \ dimension 5 \ construction fastCBC \ figureofmerit CU:P2 \ multilevelfilters norm:P2DPW08 lowpass:1.0 \ weights product:0.1 \ combiner sum
and have obtained the generating vector \(\boldsymbol a=(1,45,101,41,25)\). Then, you find out that you need to extend the number of points to \(2^9\). This can be done with:
latbuilder \ latticetype ordinary \ size "2^9" \ dimension 5 \ construction "extend:2^8:1,45,101,41,25" \ figureofmerit CU:P2 \ weights product:0.1
Note that only the merit value of the lattice with \(2^9\) points, and not that of the embedded lattices, is considered in this type of construction. The argument size "2^9"
specifies the extended number of points and the argument construction "extend:2^8:1,45,101,41,25"
indicates that we want to extend on a lattice with \(2^8\) points and generating vector \(\boldsymbol a=(1,45,101,41,25)\).
The latbuilder
executable supports the following commandline options:
latticetype
/ l
ordinary
to search for ordinary lattices; orembedded
to search for embedded lattices. size
/ n
numberOfPoints
; orprimeBase^power
. figureofmerit
/ m
Required. Specifies the accumulator type and figure of merit to be used. Takes an argument of either of the following forms:
accumulator:figure
CU:accumulator:figure
where the optional prefix CU:
indicates that a coordinateuniform implementation of the evaluation algorithm should be used;
and where figure
is one of:
spectral
for the spectral figure of merit;Palpha
for the weighted \(\mathcal P_\alpha\) figure of merit with \(\alpha=\)alpha
; orRalpha
for the weighted \(\mathcal R_\alpha\) figure of merit with \(\alpha=\)alpha
. normtype
/ p
realNumber
for a finite number;inf
for infinity. construction
/ c
Required. Specifies the search space or construction method. Takes an argument of the form:
explicit:genVec
to just compute the merit value of the lattice with generating vector genVec
specified as a list commaseparated integers;exhaustive
for exhaustive search;random:samples
for a random search with samples
random samples;Korobov
for a Korobov search;randomKorobov:samples
for a random Korobov search with samples
random samples;CBC
for a componentbycomponent search;randomCBC:samples
for a random componentbycomponent search with samples
random samples per coordinate;fastCBC
for a fast CBC search (requires a coordinateuniform implementation of the selected figure of merit);extend:numberOfPoints:genVec
to extend the number of points on a lattice with number of points numberOfPoints
and generating vector genVec
specified as a list commaseparated integers.Because the implementation of the fast CBC algorithm in lattice builder supports only numbers of points that are an integer power of a prime base, it can only be applied to embedded lattices.
When the random variant of a search is used with a filters (see the filters
option below), the candidate samples that are rejected by the filter pipeline are not considered as valid samples, meaning that the userspecified number of random samples corresponds to only the number of accepted candidates.
weights
/ w
Required. Specifies the type(s) of weights and their values. Takes a whitespaceseparated list of arguments, each of which specifying a type of weights with its values. (The actual weights are the sum of these.) Takes argument of the form:
product:default:list
for product weights with the weights for the first coordinates specified by the commaseparated list of weights list
, and with weight default
for the other coordinates;orderdependent:default:list
for orderdependent weights with the weights for the first orders specified by the commaseparated list of weights list
(starting at order 1), and with weight default
for the other orders;projectiondependent:filename
for projectiondependent weights specified in the file named filename
.POD:default1:list1:default2:list2
for POD weights, where default1
and list1
specify the default and individual orderdependent weights, and where default2
and list2
specify the default and individual product weights.For projectiondependent weights, the file containing the weights must consist of lines of the form:
coordinates: weight
to assign the weight weight
to the projection defined by the commaseparated list of coordinates coordinates
;order order: weight
to assign the weight weight
to all other projections of order order
;default: weight
to assign the weight weight
to all other projections;#comment
to ignore comment
.dimension
/ d
filters
/ f
Optional. Configures filters for merit values. Takes a whitespaceseparated list of arguments of the form:
norm:type
for a normalizer for the weighted \(\mathcal P_\alpha\) discrepancy based on the norm of type specified by type
;lowpass:threshold
for a lowpass filter with thresold value threshold
;where type
is one of:
multilevelfilters
/ F
Optional. Configures filters for the individual merit values of each nested level. Takes the same values as the filters
argument, except that, in the case of a normalization filter, weights can be optionally specified by appending :even:minLevel,maxLevel
to the filter specification, which sets even weights across all levels ranging from minLevel
through maxLevel
, and a zero weight for other levels.
combiner
/ b
Optional. Selects a combiner for multilevel figures of merit. Takes one of the following values:
sum
to sum the individual merit values of all nested levels;max
to select the maximum individual merit value across all nested levels;level:max
to select the individual merit value of the nested level with the largest number of points (the highest level);level:m
to select the individual merit value of the \(m\)th nested level.meritdigitsdisplayed
Optional. Sets the number of significant figures to use when displaying merit values. Takes a positive integer as its argument.