Lattice Tester Guide  1.0-9
Software Package For Testing The Uniformity Of Integral Lattices In The Real Space
Lattice Tester Guide Documentation

Overview

This is the user guide and API documentation of LatticeTester, a library intented to simplify the construction of software studying lattices. LatticeTester is open source software distributed with the Apache License 2.0 available on Github.

Content Outline

This page contains a summary description of the contents and the use case of LatticeTester. The rest of the guide covers the following:

  • Tutorial showcase the usage of LatticeTester and presents what the most important classes of the library. It is a good starting point to start programming with the library right away.
  • Usage instructions presenting the installation process (the dependencies and the compilation process) and the usage of an executable bundled with LatticeTester to perform high-level use of the library.
  • Background contains theory to get more familiar with lattices and the algorithms of LatticeTester
  • The full API documentation is also available in the Namespaces and Classes tabs.
  • Getting back to Github

The API documentation is automatically generated by Doxygen.

Presentation of Lattice Tester

LatticeTester is a C++ library to perform various computations on lattices \(L_t\) in the \(t\)-dimensional rational space. Lattices are discrete subgroups of a vector space (generally, the set of all integer combinations of a basis of said vector space) encountered, as an example, in the analysis of quasi-Monte Carlo point sets and certain kinds of pseudo-random number generators.

LatticeTester can perform most of its operations either on the lattice spanned by \(v_1, \ldots, v_s \in \mathbb{Q}^t\), \(L_t = \{\sum_{i=1}^s a_i v_i \ | \ a_i \in \mathbb{Z}\}\), or its m-dual lattice, \(mL_t^* = \{w \ | \ w \cdot v \in m\mathbb{Z}, \ \forall v \in L_t\}\). To do so, lattices are stored as a basis, a minimal (of cardinality \(t\) set of generating vectors \(\{v_1, \ldots, v_t\} \in L_t\), rescalled to only have integer coordinates. Vectors are stored as integer so that all the computations are done exactly on the lattice. LatticeTester only accepts integer lattices and lattices need to be rescalled before being given as input. Note that \(mL_t^*\) is also stored as integer vectors. In fact, \(m\) is choosen so that \(L_t^* \subset \mathbb{Q}^t\) becomes \(mL_t^* \subset\mathbb{Z}^t\).

The main goal of this library is to implements and/or facilitate the computation of theoretical measure of uniformity (or figures of merit) on lattices, as it is the main concern when studying pseudo-random point sets [11][20]. To perform these algorithms efficiently, LatticeTester also implements a handfull of handy lattices manipulations:

  1. Lattice Basis Construction: Given a set of vectors that are not necessarily independent but span a lattice, find a basis for that lattice.
  2. Dual Lattice Basis construction: Given a lattice basis for \(L_t\), compute the corresponding m-dual lattice basis for \(mL_t^*\) whether \(m\) is known or not.
  3. Lattice Basis Reduction: Given a lattice basis, find another basis whose vectors are nearly orthogonal or as short as possible. There are many variants and definitions for this, such as the well known LLL reduction which is available.
  4. Shortest Vector computation: Find the shortest non-zero vector in a lattice, and prove it is the shortest.

The measures of uniformity that are considered by this software are the spectral test, that is the inverse length of the shortest vector in the dual lattie, and the Beyer ratio, which is an old test ([3]) inlcuded mainly as part of our legacy code base. Building on those mesures of uniformity, LatticeTester also implements classes that help constructing figures of merit. Figures of merit are a recurring theme in quasi-Monte Carlo point set studies [14]. A figure of merit is a standardized measure that can be used to compare point sets between them. Generally, they are constructed as a weighted sum, or the minimum of weighted values :

\[ \min_{i \subset I} \omega_i \ell_i \]

with \(I\), a set of indices, \(\omega_i\) being weights and \(\ell_i\) a mesure on the projection of a lattice on set of indices \(i\).

Finaly, for the sake of convenience, LatticeTester also features a high-level executable that can perform, without much flexibility, some of the computations featured in LatticeTester. Its usage is described in Usage instructions

LatticeTester is not intended as a tool to search for lattices that conform to certain prerequisites, but instead it can be extended with a few classes to do so. LatNet Builder and LatMRG are software tools designed in our laboratory that are examples of the capabilities of this library. The first one is designed to analyze and search for lattice rules for quasi-Monte-Carlo integration whilst the second does something similar for linear congruential pseudo-random number generators.

Types and representations

Before diving into the features of LatticeTester lets look at what is NOT a feature of this library, but is needed by it: the ability to manipulate numbers with arbitrary size and precision with decent efficiency. To do that, we use another library called the Number Theory Library, more commonly called NTL. Anyone using LatticeTester will need to use some of the functionnalities of NTL at one point. Many basic mathematical functions require using this library directly. Its documentation can be found at https://www.shoup.net/ntl/. Note that LatticeTester also expands the NTL namespace. This extension contains overloads of NTL functions to non-NTL types to ease the usage of LatticeTester with NTL and non-NTL types in the same code.

Links