Lattice Builder Manual
Software Package for Constructing Rank-1 Lattices
Command-Line Tutorial

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:

  1. Recipes
  2. Summary of Command-Line Options

The following typesetting semantics is adopted:

  • verbatim for text to be typed as is;
  • arg for text to be substituted;
  • when a command is broken into multiple lines, a trailing backslash (\) indicates that the command is continued on the next line.

Recipes

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.

  • The argument --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.
  • The argument --size 2053 indicates that we seek a lattice rule with 2053 points.
  • The argument --dimension 5 specifies that we seek a lattice point set of dimension 5.
  • The argument --construction CBC specifies that a CBC construction should be used. Specifying other construction methods is explained in Construction Type.
  • The argument --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.
  • The argument --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:

  1. Specifying the Weights
  2. Figures of Merit
  3. Filtering Merit Values
  4. Construction Type
  5. Embedded Lattices
  6. Extensible Lattices

Specifying the Weights

Projection-Dependent Weights

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.

Order-Dependent Weights

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\).

  • Order-dependent weights with \(\Gamma_\ell^2 = 0.3\) for all \(\ell\):
      --weights order-dependent:0.3
  • Order-dependent weights with \(\Gamma_1^2 = 1.0\), \(\Gamma_2^2 = 0.7\), \(\Gamma_3^2 = 0.3\) and \(\Gamma_\ell^2 = 0.1\) for all \(\ell \geq 4\):
      --weights order-dependent:0.1:1.0,0.7,0.3

Product Weights

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\).

  • Product weights with \(\gamma_j^2 = 0.3\) for all \(j\):
      --weights product:0.3
  • Product weights with \(\gamma_1^2 = 1.0\), \(\gamma_2^2 = 0.7\), \(\gamma_3^2 = 0.3\) and \(\gamma_j^2 = 0.1\) for all \(j \geq 4\):
      --weights product:0.1:1.0,0.7,0.3

POD Weights

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.

  • POD weights with \(\Gamma_1^2 = 1.0\), \(\Gamma_2^2 = 0.7\), \(\Gamma_3^2 = 0.3\) and \(\Gamma_\ell^2 = 0.1\) for all \(\ell \geq 4\), and with \(\gamma_1^2 = 1.0\), \(\gamma_2^2 = 0.9\), \(\gamma_3^2 = 0.7\) and \(\gamma_j^2 = 0.5\) for all \(j \geq 4\):
      --weights POD:0.1:1.0,0.7,0.3:0.5:1.0,0.9,0.7

Figures of Merit

  • The spectral figure of merit (weighted worst projection):

    \[ \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
  • The spectral figure of merit (weighted average):

    \[ \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 spectral
    The optional third colon-separated token specifies the exponent applied to the square brackets. It defaults to 1, as in the previous example.
  • The \(\mathcal P_\alpha\) discrepancy with \(\alpha=2\), using a term-by-term evaluation of the sum with an \(\ell_q\) norm with \(q=1.5\):
        --figure-of-merit P2 --norm-type 1.5
  • The \(\mathcal P_\alpha\) discrepancy with \(\alpha=4\), using term-by-term evaluation of the sum:
        --figure-of-merit P4
  • The \(\mathcal P_\alpha\) discrepancy with \(\alpha=4\), using a coordinate-uniform evaluation algorithm:
        --figure-of-merit CU:P4
  • The \(\mathcal R_\alpha\) criterion with \(\alpha=1\), using a coordinate-uniform evaluation algorithm:
        --figure-of-merit CU:R1
  • The normalized \(\mathcal P_\alpha\) discrepancy with \(\alpha=2\), using the bound from [18] :
        --figure-of-merit CU:P2 --filters norm:P2-SL10
    Usage of the --filters option is illustrated in Filtering Merit Values.

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.

  • Normalization using a bound on \(\mathcal P_\alpha\) from [18] with \(\alpha=2\):
        --filters norm:P2-SL10
    The 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\).
  • Normalization using a bound on \(\mathcal P_\alpha\) from [5] (available only when using product weights) with \(\alpha=2\):
        --filters norm:P2-DPW08
  • Rejecting candidate lattices that have a normalized merit value larger than unity:
        --filters norm:P2-SL10 low-pass:1.0
    The 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 Type

  • Simply evaluate the figure of merit for a lattice rule with generating vector \((1, 468, 896, 603, 367)\):
      --construction explicit:1,468,896,603,367
  • Search among all possible generating vectors:
      --construction exhaustive
  • Search among 1000 randomly picked generating vectors:
      --construction random:1000
  • Search among 1000 randomly picked generating vectors that have a normalized \(\mathcal P_2\) value smaller than unity:
      --construction random:1000 --filters norm:P2-SL10 low-pass:1.0
  • Search among all possible generating vectors for Korobov lattices:
      --construction Korobov
  • Search among 30 randomly picked generating vectors for Korobov lattices:
      --construction random-Korobov:30
  • Perform a standard CBC construction:
      --construction CBC
  • Perform a CBC construction by considering only 10 randomly chosen values for each component of the generating vector:
      --construction random-CBC:10
  • Perform a CBC construction by considering only 10 randomly chosen values for each component of the generating vector with a corresponding normalized \(\mathcal P_2\) value smaller than unity:
      --construction random-CBC:10 --filter norm:P2-SL10 low-pass:1.0
  • Perform a fast CBC construction:
      --construction fast-CBC

Embedded Lattices

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:

  • the figure of merit is evaluated for each nested level;
  • optionally, multilevel filters are applied to the individual merit values of each nested level;
  • these filtered individual merit values are combined into a single value;
  • optionally filters are applied to this combined value to produce a final compound merit value. This mechanism can be selected in Lattice Builder by changing the lattice type to embedded with:
    --lattice-type embedded
    
  • To build embedded lattices with CBC construction in dimension 5 with \(n=2^m\) points with \(m=1,\dots,16\) using the maximum value of the spectral merit across all levels, with the same weight for all projections:
      latbuilder \
        --lattice-type embedded \
        --size "2^16" \
        --dimension 5 \
        --construction CBC \
        --figure-of-merit spectral \
        --weights product:1.0 \
        --combiner max
    The 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.
  • To build embedded lattices with fast CBC construction in dimension 10 with \(n=2^m\) points with \(m=8,\dots,16\), using a weighted sum of the normalized values of the \(\mathcal P_2\) figure of merit with product weights, and rejecting any candidate lattice that has such an individual normalized merit value larger than unity, as proposed in [5] , with the even weights across all levels:
      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 sum
    The --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

Extensible Lattices

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)\).

Summary of Command-Line Options

The latbuilder executable supports the following command-line options:

--lattice-type / -l
Required. Specifies the lattice size. Takes one of the following values:
  • ordinary to search for ordinary lattices; or
  • embedded to search for embedded lattices.
--size / -n
Required. Specifies the lattice size. Takes an argument of either form:
  • numberOfPoints; or
  • primeBase^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; or
  • Ralpha for the weighted \(\mathcal R_\alpha\) figure of merit with \(\alpha=\)alpha.
--norm-type / -p
Optional (default: 2). Specifies the type of L_p norm to combine the merit values across projections. Takes an argument of the form:
  • 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
Required. Specifies the dimension. Takes an integer argument.
--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:

  • Palpha-SL10 for the bound from [18] ; or
  • Palpha-DPW08 for the bound from [5] (available only with product weights);

--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.