Lattice Builder Manual Software Package for Constructing Rank-1 Lattices

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Modules Pages
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.