This is an old revision of the document!
mptopcom
mptopcom is a software developed at TU Berlin and Hokkaido University for computing triangulations of point configurations in parallel. It is a combination of
Our arXiv paper describes the algorithm and contains many details as well as examples. Please cite this reference in your papers if you are using mptopcom.
Prerequisites
Please read this very carefully! mptopcom is highly optimized software dedicated to exceptionally large enumerations on suitable hardware. As a consequence it depends on a number of up-to-date-versions of other software, and the installation requires some diligence.
You need to have open-mpi or some other mpi implementation and polymake version at least 3.2 installed. In particular, you need the polymake callable library, which might not be installed by the package manager of your distribution. Furthermore, you need an installation of cdd, the bundled version coming with polymake does not build the cdd library.
mptopcom has been tested with several versions, at least 5.3.0, of gcc and clang, at least version 3.8.0. For MPI we have tested openmpi at least version 1.4.1 and Intel MPI 20150128.
Download
Here are download links to tarballs containing the sources of mptopcom:
Installation
Installation can be done with the following three commands:
./configure ninja -C build/Opt -j #CPU's ninja -C build/Opt install
There are several options to the ./configure
command that can be viewed with
./configure --help
The most important options are
--with-polymake=/path/to/polymake/installation --with-mpi=/path/to/mpi/installation --prefix=/path/to/install/dir
The configure command will extract most of the information needed from polymake's polymake-config
command.
The binaries are in the build/Opt/bin
folder after building and in the prefix/bin
folder after installation. Besides the usual TOPCOM binaries there are two new binaries:
- mptopcom1: Runs reverse search single threaded.
- mptopcom: Multithreaded reverse search.
You can test your build by running the testsuite:
perl testsuite.pl
Usage
Input files are formated as in TOPCOM, please have a look at the files in the examples
folder for samples. You can then call mptopcom in the following way:
mpirun -np 5 mptopcom < examples/cube_4.dat
If you did not run make install
you can call the binary in the build/Opt/bin
folder:
mpirun -np 5 ./build/Opt/bin/mptopcom < examples/cube_4.dat
This will produce all triangulations of the four dimensional cube.
There are several options you can invoke to modify the behaviour of mptopcom:
Options
-F
: Only list full/fine/spanning triangulations--flip_cache n
: Sets size of flip cache to n (default: 50)--make_marked_tree
: Draws a tree with classes having the same node color (mptopcom1
only)--make_tree
: Will produce polymake code to plot reverse search tree (mptopcom1
only)--regular
: Only output regular triangulations--orbit_cache n
: Size of symmetry cache set to n (default: 50)-v
: verbose (every worker will tell when he found 1000 triangulations)
Budgeting options
-maxnodes
only affects the “bumps” at maxnodes and scale*maxnodes.-scale
sets the scaling factor when we have many jobs available (workers can work longer if we aren't trying to split jobs)-maxd
sets the max depth to go to when we don't have enough jobs available (2 is the default, which is aggressive. 0 disables)-lmax
sets the point where -scale is used (if |L| > lmax * numproc)-lmin
sets the point where -maxd is used (if |L| < lmin * numproc)
Checkpointing and restarting
mts supports checkpointing and restarts; if you add options -checkp file1 -stop file2
then it will periodically check to see if file file2 exists, and if so then it will checkpoint to file1 when convenient (it waits for workers to finish their current jobs first). Then you can restart using option -restart file1
(and of course can use -checkp & -stop again, but you should give different filenames to the -restart and -checkp options). There is an example in the section below.
Sample usage
This section contains samples of how to call mptopcom1
and mptopcom
using the above options. It is assumed that mptopcom was build, but not installed and that the current directory is the root of the source directory.
mptopcom1
./build/Opt/bin/mptopcom1 < examples/cube_3.dat ./build/Opt/bin/mptopcom1 -v < examples/cube_3.dat ./build/Opt/bin/mptopcom1 -v < examples/moae.dat ./build/Opt/bin/mptopcom1 -v --regular < examples/moae.dat ./build/Opt/bin/mptopcom1 -v --regular -F < examples/moae.dat ./build/Opt/bin/mptopcom1 -v --flip_cache 2000 --orbit_cache 2000 < examples/moae.dat ./build/Opt/bin/mptopcom1 -v --make_tree < examples/moae.dat
mptopcom
mpirun -np 8 ./build/Opt/bin/mptopcom < examples/cube_3.dat mpirun -np 8 ./build/Opt/bin/mptopcom -v < examples/cube_3.dat mpirun -np 8 ./build/Opt/bin/mptopcom --regular < examples/cube_4.dat mpirun -np 10 ./build/Opt/bin/mptopcom < examples/lattice_3_3.dat mpirun -np 10 ./build/Opt/bin/mptopcom -F < examples/lattice_3_3.dat mpirun -np 10 ./build/Opt/bin/mptopcom -F --flip_cache 2000 --orbit_cache 2000 < examples/lattice_3_3.dat mpirun -np 10 ./build/Opt/bin/mptopcom < examples/lattice_3_3.dat 1>output.txt 2>error.txt
The following is an example for checkpointing and restarting:
mpirun -np 8 ./build/Opt/bin/mptopcom -v -stop stop_file -checkp checkp_file < examples/cube_4.dat touch stop_file
Now the state will be written to the file checkp_file
and after a while the computation stops. Restart it with
mpirun -np 8 ./build/Opt/bin/mptopcom -v -restart checkp_file < examples/cube_4.dat
Drawing the reverse search tree
mptopcom1
can output polymake code that one can paste into polymake to obtain the reverse search tree in the edge graph of the secondary polytope. This will not work for large examples, so handle with care. There are three possibilities:
Give mptopcom1
an example without symmetry group:
./build/Opt/bin/mptopcom1 --make_tree < mp_examples/nosym/moae.dat
This will just draw all nodes in the same color and the edges between them that the reverse search used.
Give mptopcom1
an example with symmetry group:
./build/Opt/bin/mptopcom1 --make_tree < examples/moae.dat
Now just the canonical representatives are drawn and the edges between them come from the reverse search, but they do not have to correspond to edges of the secondary polytope, since there can be a flip between classes of triangulations, while there is no flip between the canonical representatives.
Give mptopcom1
an example with symmetry group and the parameter –make_marked_tree:
./build/Opt/bin/mptopcom1 --make_marked_tree < examples/moae.dat
This call will make mptopcom1
ignore the symmetry group. So the node number and the edges are the same as in 1. However, the tree generating procedure will use the symmetry group to color nodes according to their class membership.
Authors
mptopcom is joint work of the following three authors:
- Skip Jordan, Laboratory for Algorithmics, Hokkaido University, Japan
- Michael Joswig, Department of Mathematics, TU Berlin, Germany
- Lars Kastner, Department of Mathematics, TU Berlin, Germany
mptopcom is based on TOPCOM which is developed by
- Jörg Rambau, Department of Mathematics, Universität Bayreuth, Germany
License
mptopcom is licensed under the GNU General Public License version 3. mptopcom is based on TOPCOM, which is licensed under the GNU General Public License version 2, but allows redistributing its code under newer versions of the GPL. For configuring and installing mptopcom contains perl scripts from polymake that have been adapted to the setting of mptopcom. polymake is licensed under the GNU General Public License version 2, but allows redistributing its code under newer versions of the GPL.
See the files COPYING
and LICENSE
in the source for further details.