# 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](http://www.rambau.wm.uni-bayreuth.de/TOPCOM/)** for triangulations,
- **[polymake](https://polymake.org/doku.php)** for combinatorics, and
- **[mts](http://cgm.cs.mcgill.ca/~avis/doc/tutorial.html)** for parallelising reverse search.

Please see our **[arXiv article](https://arxiv.org/abs/1709.04746)** for further details on the algorithms.

## Prerequisites
You need to have **[open-mpi](https://www.open-mpi.org/)** and
**[polymake](https://polymake.org/doku.php)** version at least 3.2 installed. In
particular, you need the **[polymake callable
library](https://polymake.org/doku.php/reference/callable)**, which might not
be installed by the package manager of your distribution. Furthermore, you need
an installation of
**[cdd](https://www.inf.ethz.ch/personal/fukudak/cdd_home/)**, 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**:

- [mptopcom-1.0.tar.bz2](https://polymake.org/lib/exe/fetch.php/download/mptopcom-1.0.tar.bz2)

## 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


1.  `-F` : Only list full/fine/spanning triangulations
2.  `--flip_cache n` : Sets size of flip cache to n (default: 50)
3.  `--make_marked_tree` : Draws a tree with classes having the same node color (`mptopcom1` only)
4.  `--make_tree` : Will produce polymake code to plot reverse search tree (`mptopcom1` only)
5.  `--regular` : Only output regular triangulations
6.  `--symmetry_cache n` : Size of symmetry cache set to n (default: 50)
7.  `-v` : verbose (every worker will tell when he found 1000 triangulations)

### Budgeting options
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)







## 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 --symmetry_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 --symmetry_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:

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.



## Authors
**mptopcom** is joint work of the following three authors:

- **[Skip Jordan](https://www-alg.ist.hokudai.ac.jp/~skip/)**, Laboratory for Algorithmics, Hokkaido University, Japan
- **[Michael Joswig](http://page.math.tu-berlin.de/~joswig/)**, Department of Mathematics, TU Berlin, Germany
- **[Lars Kastner](http://page.math.tu-berlin.de/~kastner/)**, Department of Mathematics, TU Berlin, Germany

**mptopcom** is based on **TOPCOM** which is developed by

- **[Jörg Rambau](http://www.rambau.wm.uni-bayreuth.de/)**, Department of Mathematics, Universität Bayreuth, Germany

## License
**mptopcom** is licensed under the **[GNU General Public License version
3](https://www.gnu.org/licenses/gpl.html)**. **TOPCOM** is licensed under the
**[GNU General Public License version
2](https://www.gnu.org/licenses/old-licenses/gpl-2.0.html)**, but allows
redistributing its code under newer versions of the GPL.

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA  02110-1335  USA
