Lattice Builder Manual
Software Package for Constructing Rank-1 Lattices
|
This tutorial teaches how to use the Lattice Builder command-line tool to search for good rank-1 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 command-line 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 component-by-component (CBC) construction, which we use to introduce the different command-line options. After, we extend that example in various ways to show how to achieve different specific tasks.
Consider the following basic example:
latbuilder \ --lattice-type ordinary \ --size 2053 \ --dimension 5 \ --construction CBC \ --figure-of-merit 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.
--lattice-type ordinary
indicates that we seek an ordinary (in contrast to embedded) rank-1 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.--figure-of-merit CU:P2
consists of three colon-separated tokens. It tells Lattice Builder to use the specialized coordinate-uniform 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 coordinate-uniform 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 self-explanatory. For the sake of conciseness, in the derived examples, we only show the command-line 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 projection-dependent weights, the weight associated to the projection onto the coordinates in \(\mathfrak u\) can be set to any non-negative constant \(\gamma_{\mathfrak u}\).
The projection-dependent 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.0e-3
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 colon-separated token indicates the type (projection-dependent) 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 infinity-norm, where they are interpreted as if \(p = 1\). To interpret the numerical values as another power of the weights, say 1, the option
--weights-power 1
must be added to the command line.
With order-dependent 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 colon-separated tokens: the first is the type of weights (order-dependent 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 comma-separated list of order-dependent weights \(\Gamma_1,\dots,\Gamma_j\) for some \(j\).
--weights order-dependent:0.3
--weights order-dependent: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 colon-separated 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 comma-separated 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 order-dependent (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 colon-separated tokens: the first is the type of weights (POD), the next two specify the \(\Gamma_j\)'s as in Order-Dependent 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 projection-dependent 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:--norm-type inf --figure-of-merit spectral
\[ \sum_{\emptyset \neq \mathfrak u \subseteq \{1,\dots,s\}} \left[ \gamma_{\mathfrak u} \bar{\mathcal L}_{\mathfrak u}(n, \boldsymbol a) \right]^2 \]
--figure-of-merit spectralThe optional third colon-separated token specifies the exponent applied to the square brackets. It defaults to 1, as in the previous example.
--figure-of-merit P2 --norm-type 1.5
--figure-of-merit P4
--figure-of-merit CU:P4
--figure-of-merit CU:R1
--figure-of-merit CU:P2 --filters norm:P2-SL10Usage 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:P2-SL10The first colon-separated 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:P2-DPW08
--filters norm:P2-SL10 low-pass:1.0The first filter is explained above. The second filter consists of two colon-separated tokens: the first one (
low-pass
) indicates that we want to apply a low-pass filter on merit values; the second one specifies the threshold value of this low-pass 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:P2-SL10 low-pass:1.0
--construction Korobov
--construction random-Korobov:30
--construction CBC
--construction random-CBC:10
--construction random-CBC:10 --filter norm:P2-SL10 low-pass:1.0
--construction fast-CBC
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:
--lattice-type embedded
latbuilder \ --lattice-type embedded \ --size "2^16" \ --dimension 5 \ --construction CBC \ --figure-of-merit 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 \ --lattice-type embedded \ --size "2^16" \ --dimension 10 \ --construction fast-CBC \ --figure-of-merit CU:P2 \ --multilevel-filters norm:P2-DPW08:even:8,16 low-pass:1.0 \ --weights product:0.1 \ --combiner sumThe
--multilevel-filters
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 \ --lattice-type embedded \ --size "2^8" \ --dimension 5 \ --construction fast-CBC \ --figure-of-merit CU:P2 \ --multilevel-filters norm:P2-DPW08 low-pass: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 \ --lattice-type ordinary \ --size "2^9" \ --dimension 5 \ --construction "extend:2^8:1,45,101,41,25" \ --figure-of-merit 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 command-line options:
--lattice-type
/ -l
ordinary
to search for ordinary lattices; orembedded
to search for embedded lattices. --size
/ -n
numberOfPoints
; orprimeBase^power
. --figure-of-merit
/ -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 coordinate-uniform 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
. --norm-type
/ -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 comma-separated integers;exhaustive
for exhaustive search;random:samples
for a random search with samples
random samples;Korobov
for a Korobov search;random-Korobov:samples
for a random Korobov search with samples
random samples;CBC
for a component-by-component search;random-CBC:samples
for a random component-by-component search with samples
random samples per coordinate;fast-CBC
for a fast CBC search (requires a coordinate-uniform 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 comma-separated 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 user-specified 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 whitespace-separated 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 comma-separated list of weights list
, and with weight default
for the other coordinates;order-dependent:default:list
for order-dependent weights with the weights for the first orders specified by the comma-separated list of weights list
(starting at order 1), and with weight default
for the other orders;projection-dependent:filename
for projection-dependent weights specified in the file named filename
.POD:default1:list1:default2:list2
for POD weights, where default1
and list1
specify the default and individual order-dependent weights, and where default2
and list2
specify the default and individual product weights.For projection-dependent 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 comma-separated 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 whitespace-separated 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
;low-pass:threshold
for a low-pass filter with thresold value threshold
;where type
is one of:
--multilevel-filters
/ -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.--merit-digits-displayed
Optional. Sets the number of significant figures to use when displaying merit values. Takes a positive integer as its argument.