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

• TOPCOM for triangulations,
• polymake for combinatorics, and
• mts for parallelising reverse search.

Our paper describes the algorithm and contains many details as well as examples. Please cite this reference in your papers if you are using mptopcom.

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

Note Having multiple versions of openmpi installed is a common source of errors. During the configuration, mptopcom will display the version of openmpi it found. Please make sure that this version, and the versions of mpirun, mpicc, and mpicxx all agree, and ideally come from the same installation.

• gcc 11.3.0, openmpi 4.1.5, polymake 4.11
• clang 18.1.1, openmpi 4.1.5, polymake 4.11

• gcc 12.2.1, openmpi 4.1.5, polymake 4.9
• gcc 7.5.0, openmpi 3.1.2-15, polymake 4.6
• gcc 7.5.0, openmpi 4.1.4, polymake 4.6
• gcc 7.5.0, openmpi 4.1.4, polymake 4.1

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.

Here are download links to tarballs containing the sources of mptopcom:

• mptopcom-1.4.tar.bz2 from 2024-03-25.

Note that this version of mptopcom contains a new algorithm for traversing the flip graph of regular triangulations, in that it checks flips for regularity rather than triangulations. The new version has been checked extensively, on the 4-cube and the 3-dilated 3-simplex and many others. Nevertheless, please let us know if you encounter any wrong results.

• mptopcom-1.3.tar.bz2 from 2022-09-01.
• mptopcom-1.2.tar.bz2 from 2020-08-28.
• mptopcom-1.1.tar.bz2 from 2019-05-29 for polymake versions before 4.0.
• mptopcom-1.1_polymake4.0.tar.bz2 from 2020-02-07 for polymake versions after 4.0.
• mptopcom-1.0r2.tar.bz2 from 2018-05-14 with a bugfix for newer polymake.

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 four new binaries:

• mptopcom1: Runs reverse search single threaded.
• mptopcom: Multithreaded reverse search.
• canonicalRepresentative: Compute the canonical representative from the orbit of a triangulation.
• randomBFS: Execute a random breadth first search on the flip-graph of triangulations, only reports the queue sizes.
• random_walk: Execute a random walk, the size can be specified with the --rw-size option.

You can test your build by running the testsuite:

perl testsuite.pl

We have had many complaints by users that tracked back to multiple versions of openmpi being installed at the same time. Hence the mpirun they were using stemmed from a different installation than the one they specified when building mptopcom. To mitigate this issue, mptopcom places a symlink to the correct mpirun in the installation.

Since mptopcom usually is used for enumerating triangulations, which is hard for larger point configurations, certain optimizations have been built which result in mptopcom only being able to handle at most 64 points.

During installation these optimizations may be turned off using

CXXFLAGS=-DWITH_PM_BITSET ./configure

The resulting mptopcom installation will be able to deal with more than 64 points, however it will be significantly slower than the mptopcom standard version.

Input files are formatted as in TOPCOM, please have a look at the files in the examples folder for samples. The points are given homogeneously, i.e. embedded at height one. After the points you can give the generators of a group acting on your point set. Here is the example of the input file for the two-dimensional 0-1-square:

[
[1,0,0],
[1,0,1],
[1,1,0],
[1,1,1]
]
[
[0,2,1,3],
[3,1,2,0],
[2,3,0,1]
]

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:

1. --cyclic-flips : Use special combinatorial description of the reverse search graph for cyclic polytopes
2. --full : Only list full/fine/spanning triangulations
3. --flip-cache n : Sets size of flip cache to n (default: 2000)
4. --make-marked-tree : Draws a tree with classes having the same node color (mptopcom1 only)
5. --make-tree : Will produce polymake code to plot reverse search tree (mptopcom1 only)
6. --orbit-cache n : Size of symmetry cache set to n (default: 2000)
7. --regular : Only output regular triangulations
8. --regularity-cache n : Size of regularity cache set to n (default: 2000)
9. -v : verbose (every worker will tell when he found 1000 triangulations)
10. --central : Produce only triangulations with maximal gkz[0], depends on ordering of points

1. -maxnodes only affects the “bumps” at maxnodes and scale*maxnodes.
2. -scale sets the scaling factor when we have many jobs available (workers can work longer if we aren’t trying to split jobs)
3. -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)
4. -lmax sets the point where -scale is used (if |L| > lmax * numproc)
5. -lmin sets the point where -maxd is used (if |L| < lmin * numproc)

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.

This section contains samples of how to call mptopcom1 and mptopcom using the above options. It is assumed that mptopcom was built, but not installed and that the current directory is the root of the source directory.

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

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 --full < examples/lattice_3_3.dat
mpirun -np 10 ./build/Opt/bin/mptopcom --full --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

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:

1. 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. 2. 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. 3. 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.

mptopcom is joint work of the following three authors:

• Skip Jordan, Department of Information and Management Science, Otaru University of Commerce, Japan
• Michael Joswig, Department of Mathematics, TU Berlin, Germany
• Lars Kastner, Department of Mathematics, TU Berlin, Germany

We are very grateful to Marta Panizzut from UiT - The Arctic University of Norway for joint work on the enhanced regularity checks.

mptopcom is based on TOPCOM which is developed by

• Jörg Rambau, Department of Mathematics, Universität Bayreuth, Germany

We are very grateful to Benjamin Lorenz for many discussions and for lending us his C++ expertise during the implementation phase.

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.