Awesome

LatNet Builder

A general software tool for constructing highly uniform point sets

LatNet Builder Manual

Outline:

1. A software for quasi-Monte Carlo
2. How to use the software
3. How to get the software
4. For developers
5. Further information

A software for quasi-Monte Carlo

LatNet Builder is a C++ software library and tool for constructing highly-uniform point sets for quasi-Monte Carlo and randomized quasi-Monte Carlo methods using state-of-the-art techniques.

Quasi-Monte Carlo methods are often used as a replacement for Monte Carlo to integrate multidimensional functions.

Monte Carlo and quasi-Monte Carlo methods are used for the same purpose. The problem is to approximate the integral of a function over the unit hypercube as the average of the function evaluated at a set of points. Whereas Monte-Carlo uses a (pseudo)-random sequence of points, quasi-Monte Carlo uses a highly uniform point set, that is a point set with low discrepancy. For certain problems, well-constructed point sets can dramatically reduce the integration error with respect to Monte Carlo.

LatNet Builder implements a variety of construction algorithms for highly uniform point sets. The point set types handled by LatNet Builder include rank-1 ordinary and polynomial lattice rules and digital nets in base 2, including Sobol' nets.

More precisely, LatNet Builder can search for point sets with an arbitrary number of points in any dimension of high quality with respect to various criteria. Such quality criteria are called figures of merit. These figures of merit are parametrized by weights which give different importance to the subprojections of the net. The merits of the subprojections are aggregated using a (weighted) 𝓁_q norm. LatNet Builder can use various exploration methods to construct the point sets, such as the exhaustive, the random sampling or the component-by-component (CBC) methods.

Additionally LatNet Builder contains more advanced features such as multilevel point sets, extensible point sets, interlaced point sets, normalizations, and filters.

The features of LatNet Builder are summed up in the following table:

How to use the software

Quick overview

The user can quickly discover the functionalities of LatNet Builder without anything to install using Binder:

This service hosts a version of LatNet Builder which can be used through a Graphical User Interface (GUI). However, this service only provides limited computation resources. For a better experience, one should install the software on their machine.

Main components

LatNet Builder offers various possibilities to use its functionalities:

• a C++ library
• a Command Line Tool
• a Python package which comprises:
  • a Python interface
  • a Graphical User Interface based on the Jupyter ecosystem
• a Java interface encapsulated in the Stochastic Simulation in Java (SSJ) software

There are four ways to get the software:

• downloading a binary release (only available for Linux and Mac OS)
• installing the Python package (with conda)
• using a Docker container, a 'light-weight virtual machine'
• compiling the source code

The binary pre-compiled release of LatNet Builder is available on itself and also wrapped in a Python package. The latter provides a one-line installation procedure for the software, its GUI and its Python interface.

The Docker container, which encapsulates a Linux distribution, is meant as a convenience for Windows users. As an additional convenience, the Python package in its Windows version acts as a wrapper above the Docker container. Users unfamiliar with Docker should thus consider using the Python package.

The source code should compile fine on Linux and Mac OS platforms. However, since a lot of dependencies are required, we advise you to use the binary pre-compiled release available either on its own or through the Python package.

For Windows users who would like to compile the source code, we recommend to use a UNIX emulation environment like Cygwin or MinGW, instead of Microsoft development tools. Compiling LatNet Builder and its dependencies may turn out to be time-consuming so we highly recommend to use the conda package or directly the Docker container.

The command-line tool in a nutshell

Information on using the LatNet Builder program is given in the LatNet Builder command line tutorial. Compact usage information can also be obtained with latnetbuilder --help.

The below command line assumes that the latnetbuilder executable was added to your PATH environment variable. It will be the case if you installed LatNet Builder with conda or are using a Docker container. If you installed a binary package, you must replace latnetbuilder with a path to the latnetbuilder executable. For instance if you installed LatNet Builder in $HOME/latnetsoft, use $HOME/latnetsoft/bin/latnetbuilder.

Constructing rank-1 lattice rules

As a concrete example of how the program can be used, the following command line performs a fast CBC exploration using the weighted P_α criterion with α=2 and with product weights giving the same weight of 0.1 to every coordinate (this means a weight of 10^-2 for projections of order 1, of 10^-4 for projections of order 2, of 10^-6 for projections of order 3, etc.):

latnetbuilder -t lattice -c ordinary -s 2^16 -d 100 -f CU:P2 -q 2 -w product:0.1 -e fast-CBC

The above search is for n=2¹⁶=65,536 points in dimension 100. LatNet Builder does that in less than 2 seconds.

Constructing digital nets

Likewise, to construct a Sobol' net with 2¹⁶ points in 10 dimensions using the random component-by-component (CBC) algorithm, with 70 samples per coordinate and a t-value-based criterion with order-dependent weights equal to 1 on the 2-dimensional and 3-dimensional projections, issue the following command:

latnetbuilder -t net -c sobol -s 2^16 -d 10 -f projdep:t-value -q inf -w order-dependent:0:0,1,1 -e random-CBC:70

The LatNet Builder library

Several examples of code using the LatNet Builder application programming interface (API) can be found under the share/doc/examples directory under the installation directory and in subdirectories.

To learn how to code using the LatNet Builder library, you can read the Library Tutorial.

Compiling and linking code with the LatNet Builder library requires the same software dependencies to be available as for compiling the LatNet Builder program itself.

External software can make use of the LatNet Builder libraries by setting the compiler to use the C++14 standard, by adding the include and lib directories (under the installation directory) to the include and library paths, respectively, then by linking with the latticetester and latnetbuilder libraries, together with the fftw3, NTL, GMP and Boost libraries.

In particular, if LatNet Builder, Boost , NTL, GMP and FFTW were respectively installed under $HOME/latnetsoft, /opt/boost, /opt/ntl, /opt/gmp and /opt/FFTW, a C++ source file called myprog.cc can be compiled and linked into an executable called myprog by using the following command line with g++:

g++ 
  -std=c++14 -O2 \
  -I$HOME/latnetsoft/include \
  -I/opt/boost/include \
  -I/opt/ntl/include \
  -I/opt/gmp/include \
  -I/opt/fftw/include \
  -o myprog myprog.cc \ 
  -L$HOME/latnetsoft/lib -l latnetbuilder -l latticetester \
  -L/opt/ntl/lib  -l ntl \
  -L/opt/gmp/lib  -l gmp \
  -L/opt/fftw/lib -l fftw3 \
  -L /opt/boost/lib -l boost_program_options -l boost_system -l boost_filesystem

With clang, just replace g++ with clang++.

How to get the software

Downloading a binary release

Binary pre-compiled releases of LatNet Builder are available for Linux and Mac OS platforms. These include the executable latnetbuilder program, library and documentation.

The binary distribution packages, under the latnetbuilder base directory, have the following directory structure:

• bin contains the executable latnetbuilder program (the command-line tool)
• include contains the C++ header files necessary to use the LatNet Builder library
• lib contains the LatNet Builder and LatticeTester libraries (LatticeTester is an embedded dependency of the LatNet Builder library)
• share/doc/latnetbuilder/ contains the HTML documentation
• share/doc/latnetbuilder/examples contains examples on using the LatNet Builder library
• share/latnetbuilder and share/latticetester contain some data files used by the libraries

Installing with conda

The Python package, which contains the binary pre-compiled release plus the GUI, must be installed using Conda. Conda is an open source package management system and environment management system, which is very popular in the Python community.

First, you have to download Conda from the Anaconda distribution. For more information, see the conda documentation about environments.

The Conda latnetbuilder package is available for Windows, Linux and Mac OS. The Windows version acts as a wrapper above a Docker container.

The installation procedures is as follow:

For Linux and MacOS

After installing Conda, you can run the following commands:

conda create -n latnetbuilder   # create a conda environment named latnetbuilder
conda config --add channels conda-forge         # add conda-forge as a default conda channel
conda install -c umontreal-simul latnetbuilder   # installs the latnetbuilder package from the channel umontreal-simul

For Windows

You have to install Docker first. Docker provides a way to run applications securely isolated in a container, packaged with all its dependencies and libraries. It is similar to a virtual machine. Depending on your Windows version, as of now, two Docker installations are available:

• for Windows 10 Professional or Enterprise 64-bit users: Docker for Windows
• for all other users: Docker Toolbox

In either case, if you are given the choice during the installation procedure, please add Docker to your PATH. Else, the configuration of LatNet Builder will require you to state the path to your Docker installation, so please remember it when you set it during the installation procedure.

The installation of Docker can be tricky, so please follow precisely the instructions on the Docker website and double-check that your installation works before moving on to the installation of LatNet Builder.

After installing Docker and Conda, you can run the following commands to install LatNet Builder:

conda create -n latnetbuilder   # create a conda environment named latnetbuilder
conda config --add channels conda-forge         # add conda-forge as a default conda channel
conda install -c umontreal-simul latnetbuilder   # installs the latnetbuilder package from the channel umontreal-simul
activate latnetbuilder  # activate the conda environment named latnetbuilder
latnetbuilder_configure # run the configuration script (which will locate the Docker installation on your system)

Running LatNetBuilder and its interface (all systems)

source activate latnetbuilder  # for UNIX
activate latnetbuilder  # for Windows
# you can call latnetbuilder from the command line:
latnetbuilder --help
# you can also start the interface:
latnetbuilder-gui

This latest command will open a Jupyter notebook in your browser. Click on the AppMode button to run the GUI in full-screen mode. For more information about Jupyter notebooks, you can have a look at the Jupyter documentation.

Remark: for Windows users with Docker Toolbox, the LatNet Builder package creates and manipulates a virtual machine. It is possible that when you shut your system down, it complains about a running VirtualBox application. This is because the LatNet Builder package does not destroy the virtual machine it creates. You can either force the shutdown of your system or destroy the machine yourself with the command docker-machine rm latnetbuilder. The next time you use LatNet Builder, the machine will be re-created.

Using a Docker container

Docker provides a way to run applications securely isolated in a container, packaged with all its dependencies and libraries. It is similar to a virtual machine.

Two Docker images are available:

• a light (446 MB) image which runs on a Linux system the binary pre-compiled executable
• a complete (1.6 GB) image which additionally contains the GUI

To install LatNetBuilder and its interface:

• install Docker
• pull the image:

docker pull umontrealsimul/latnetbuilder:complete    # for the complete image
docker pull umontrealsimul/latnetbuilder:light    # for the light image

To run LatNetBuilder and its interface: the following command starts a console inside a Docker container and tells your system to listen at port 8888 to the port 8888 of the Docker container.

docker run -it -p 8888:8888 umontrealsimul/latnetbuilder:complete bash   # for the complete image
docker run -it umontrealsimul/latnetbuilder:light bash   # for the light image

Then you can call LatNet Builder from the command line:

latnetbuilder --help

With the complete image, you can also start the interface. The following command starts a Jupyter server inside the Docker container which emits in port 8888. Once this is done, you can browse to localhost:8888 in your browser, enter the password (latnet), start the Interface.ipynb notebook, and finally click on the 'Appmode' button to start the GUI App.

Again, the password is latnet. It is only meant to secure the Jupyter server which is only useful for network applications.

latnetbuilder-gui-docker

Once you are done, do not forget to stop the Jupyter server inside the container. Even when you close the console window, the container is still running. You can see the list of running containers (and their names) with the command

docker container ls

You can either leave it running or stop it. To stop the container:

docker stop CONTAINER_NAME

If you leave it running, to start a new console you can use the following command instead of the docker run command above:

docker exec -it CONTAINER_NAME bash

Compiling the source code

This method works fine for Linux and Mac OS X users. For Windows users, the software is known to compile on Cygwin, without the --link-static option. Nevertheless, this method is really complex and we recommended you avoid it, unless you are a power user.

Software Dependencies

Compiling LatNet Builder requires the following softwares to be installed on the system:

• Python 3.6 or later
• Boost C++ Libraries 1.67.0 or later
• NTL 11.0.0 or later
• GMP compatible version with your NTL installation
• FFTW 3.3.4 or later
• Git (optional for downloading the source code)
• Doxygen (optional for generating the documentation)

You will also need a recent compiler compliant with the C++14 standard. LatNet Builder is known to compile using:

• GCC 5.4.0 on Linux
• Apple LLVM version 9.1.0 on MacOS

Obtaining the Source Code

Get the latest source tree from GitHub by typing:

git clone --recurse-submodules https://github.com/umontreal-simul/latnetbuilder.git

The --recurse-submodules clones at the same time LatticeTester, which is a subrepository of LatNet Builder.

If Git is not available on your system, you can click on the Download ZIP link from the LatNet Builder GitHub page, then by unzipping the downloaded archive. In this case, the latticetester folder is empty, so you need to also download a ZIP archive of LatticeTester, unzip it and copy the contents inside the latticetester folder.

Configuring the Build

LatNet Builder relies on the waf meta build system for configuring and compiling the software source. Waf is included in the LatNet Builder source tree, but it depends on Python, which must be available on the system on which LatNet Builder is to be compiled.

The commands below should work verbatim under Linux and MacOS systems.

Change the current directory to the root directory of the package, for example:

cd latnetbuilder

if you obtained the source code with the git command. If you obtained the source code from the ZIP archive, the directory should be named latnetbuilder-master instead of latnetbuilder. At the root of the source tree lies the waf script which manages the build process.

Try:

./waf --help

to see the various commands and options. The most relevant options include --out to specify the directory in which the files created during the build process will be placed, --prefix to specify the directory under which you wish to install the LatNet Builder software once it is compiled, and --boost, --ntl, --gmp and --fftw to specify the directories under which Boost, NTL, GMP and FFTW were installed, if not under standard system directories. First, the project must be configured with:

./waf configure --prefix $HOME/latnetsoft

with $HOME/latnetsoft replaced with the directory into which you wish to install LatNet Builder. Here, $HOME will expand to your own home directory; you can specify any other directory to which you have permissions for write access, e.g., with --prefix /tmp/latnetsoft.

If Boost, NTL, GMP and FFTW are not part of the standard system installation and were manually installed under, say, the /opt/boost, /opt/ntl, /opt/gmp and /opt/fftw directories — which means that /opt/boost, /opt/ntl, /opt/gmp and /opt/fftw both contain subdirectories named include and lib — the following command indicates waf where to find these two libraries:

./waf configure --prefix $HOME/latnetsoft --boost /opt/boost --ntl /opt/ntl --gmp /opt/gmp --fftw /opt/fftw configure --link-static

The --link-static option suggested above will cause the libraries to be linked statically to the executable program, which may be desirable especially if these are not installed in standard locations.

It is possible to set the CXX environment variable to the path to a specific C++ compiler to be used to build LatNet Builder, before running the waf configure command.

The above waf configure commands configures waf for a minimal build, without documentation, code examples nor GUI. These can be built by appending the following options to waf configure:

• --build-docs to generate the documentation, if Doxygen is available on the system.

• --build-examples to compile and install example code, including code from the tutorial, which will also be verified to yield correct output. The expected outputs are stored in text files with names matching those of programs, under the examples/tutorial/output subdirectory.

• --build-conda to build the Python package then install it in a latnetbuilder conda environment. More precisely, the package contains the LatNet Builder software and its Python interface. Thus, with this option, two versions of the software are installed: one in your installation folder, and one wrapped inside the Python package.

Errors will be reported if required software components cannot be found. In that case, you should check the dependencies installation paths.

Building and Installing

Once everything is configured correctly, the following command will build the LatNet Builder library and command-line tool:

./waf build

If the build process completed without errors, LatNet Builder can be installed to $HOME/latnetsoft, or any directory specified with the --prefix options during the configuration step, with:

./waf install

The LatNet Builder executable can be found at $HOME/latnetsoft/bin/latnetbuilder.

Before executing the LatNet Builder program, it may be necessary to to add the paths to the Boost, NTL, GMP and FFTW libraries to the LD_LIBRARY_PATH (for Linux) or to the DYLD_FALLBACK_LIBRARY_PATH (for MacOS) environment variables, especially if you did not use the --link-static option on waf configure. For example, if you're using an sh-compatible shell and Boost, NTL, GMP and FFTW were manually installed under the /opt/boost, /opt/ntl, /opt/gmp and /opt/fftw directories, respectively, type:

export LD_LIBRARY_PATH=/opt/boost/lib:/opt/ntl/lib:/opt/gmp/lib:/opt/fftw/lib:$LD_LIBRARY_PATH

under Linux, or

export DYLD_FALLBACK_LIBRARY_PATH=/opt/boost/lib:/opt/ntl/lib:/opt/gmp/lib:/opt/fftw/lib:$LD_LIBRARY_PATH

under MacOS.

To check that the program installed correctly, run:

$HOME/latnetsoft/bin/latnetbuilder --version

which should report the current LatNet Builder version. Help on usage can be obtained by replacing the --version switch with the --help switch.

For developers

Binary pre-compiled releases

To compile a portable executable, you first need to compile a portable static library for each dependency (GMP, NTL, Boost and FFTW). If the libraries are somewhere in your path (typically in /usr/local/lib), we advise to remove them beforehand, to make sure dynamic libraries do not get linked by error.

The following commands should do the job.

• If you compile on Linux:
  • replace <OS> by linux
  • add -fPIC to the list of CXXFLAGS and CFLAGS for FFTW, GMP, NTL
  • add cxxflags=-fPIC cflags=-fPIC to the ./b2 command for Boost
• If you compile on Mac OS X:
  • replace <OS> by darwin
  • add --enable-assembly=no to the configuration of GMP
  • replace --with-toolset=gcc by --with-toolset=clang
  • remove from the installation folder of Boost the shared libaries (.dylib) after installation

FFTW

export CXXFLAGS='-m64 -march=k8'
export CFLAGS='-m64 -march=k8'
./configure --prefix=$HOME/fftw --enable-static --enable-threads --with-combined-threads --enable-sse2
make
make install

GMP

export CXXFLAGS='-m64 -march=k8'
export CFLAGS='-m64 -march=k8'
./configure --prefix=$HOME/gmp --enable-shared=no --host=x86_64-unknown-<OS>-gnu
make
make install

NTL

./configure "CXXFLAGS=-O2 -m64 -march=k8 -std=c++11" GMP_PREFIX=$HOME/gmp PREFIX=$HOME/ntl NTL_THREADS=off
make
make install

Boost

./bootstrap.sh --prefix=$HOME/boost --with-toolset=gcc --without-icu --with-libraries=program_options,system,filesystem
./b2 -j4 --prefix=$HOME/boost --layout=tagged link=static threading=single variant=release target-os=<OS> address-model=64
./b2 install

LatNet Builder

./waf configure --prefix=$HOME/latnetsoft --fftw=$HOME/fftw --gmp=$HOME/gmp --ntl=$HOME/ntl --boost=$HOME/boost --link-static --build-examples --build-docs --build-conda
./waf build
./waf install

Publish a new release on the release page and update the features below.

Updating the documentation

See the README file on the gh-pages branch.

Updating the Python package on Anaconda Cloud

See the README file in the python-wrapper directory.

Updating the Docker images on DockerHub:

To update the complete docker image, run from the source code directory:

docker login
docker build -t umontrealsimul/latnetbuilder:complete --no-cache -f DockerfileComplete .
docker push umontrealsimul/latnetbuilder:complete

To update the light docker image, run from the installation directory on a Linux machine:

docker login
docker build -t umontrealsimul/latnetbuilder:light --no-cache -f share/latnetbuilder/DockerfileLight .
docker push umontrealsimul/latnetbuilder:light

Maintaining the online GUI on Binder

Binder uses the GitHub repository to build the online GUI. More precisely, it uses the environment.yml file to build the online GUI: it downloads the latnetbuilder package from Anaconda Cloud, and creates a Docker image to run the Interface.ipynb notebook.

Therefore, to re-build the online GUI, you have to:

• first upload the new version of the package to Anaconda Cloud
• then , after a new push on the master branch, the first connection will trigger a rebuild of the online GUI.

Further information

Publications

P. L'Ecuyer, P. Marion, M. Godin, and F. Puchhammer, A Tool for Custom Construction of QMC and RQMC Point Sets, Monte Carlo and Quasi-Monte Carlo Methods 2020, submitted. arXiv link.

P. Marion, M. Godin, and P. L'Ecuyer, An algorithm to compute the t-value of a digital net and of its projections, Journal of Computational and Applied Mathematics, volume 371, paper 112669, June 2020. arXiv link.

P. L'Ecuyer and D. Munger, Algorithm 958: LatticeBuilder: A General Software Tool for Constructing Rank-1 Lattice Rules, ACM Transactions on Mathematical Software, 42, 2 (2016), Article 15. Online access.

See also the reports folder for internship reports on LatNet Builder.

Contributors

This project was supervised by Pierre L'Ecuyer in the Département d’Informatique et de Recherche Opérationnelle at the Université de Montreal.

List of contributors (by alphabetical order):

• Yocheved Darmon
• Maxime Godin
• Ayman Jemel
• Pierre Marion
• David Munger