Both sides previous revision Previous revision Next revision | Previous revision Next revisionBoth sides next revision |
mptopcom [2019/03/01 13:21] – mptopcom page: Update callable library link lkastner | mptopcom [2020/06/05 11:51] – input file example lkastner |
---|
* **[[http://cgm.cs.mcgill.ca/~avis/doc/tutorial.html|mts]]** for parallelising reverse search. | * **[[http://cgm.cs.mcgill.ca/~avis/doc/tutorial.html|mts]]** for parallelising reverse search. |
| |
Our **[[https://arxiv.org/abs/1709.04746|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. | Our **[[https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p6|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 ===== | ===== 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. | 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 **[[https://www.open-mpi.org/|open-mpi]]** or some other mpi implementation and **[[https://polymake.org/doku.php|polymake]]** version at least 3.2 installed. In particular, you need the **[[https://polymake.org/doku.php/callable|polymake callable library]]**, which might not be installed by the package manager of your distribution. Furthermore, you need an installation of **[[https://www.inf.ethz.ch/personal/fukudak/cdd_home/|cdd]]**, the bundled version coming with polymake does not build the cdd library. | You need to have **[[https://www.open-mpi.org/|open-mpi]]** or some other mpi implementation and **[[https://polymake.org/doku.php|polymake]]** version at least 3.2 installed. In particular, you need the **[[https://polymake.org/doku.php/reference/callable|polymake callable library]]**, which might not be installed by the package manager of your distribution. Furthermore, you need an installation of **[[https://www.inf.ethz.ch/personal/fukudak/cdd_home/|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. | **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**: | Here are download links to tarballs containing the sources of **mptopcom**: |
| |
* [[https://polymake.org/lib/exe/fetch.php/download/mptopcom-1.0r1.tar.bz2|mptopcom-1.0.tar.bz2]] | * [[https://polymake.org/lib/exe/fetch.php/download/mptopcom-1.1.tar.bz2|mptopcom-1.1.tar.bz2]] from 2019-05-29 for polymake versions before 4.0. |
| * [[https://polymake.org/lib/exe/fetch.php/download/mptopcom-1.1_polymake4.0.tar.bz2|mptopcom-1.1_polymake4.0.tar.bz2]] from 2020-02-07 for polymake versions after 4.0. |
| |
| Note that recent changes in polymake were breaking, so only the second version works with polymake 4.0 and newer. |
| |
| ==== Old versions ==== |
| |
| * [[https://polymake.org/lib/exe/fetch.php/download/mptopcom-1.0r2.tar.bz2|mptopcom-1.0r2.tar.bz2]] from 2018-05-14 with a bugfix for newer polymake. |
| |
===== Installation ===== | ===== Installation ===== |
The configure command will extract most of the information needed from polymake's ''%%polymake-config%%'' command. | 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: | 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. | * **mptopcom1**: Runs reverse search single threaded. |
* **mptopcom**: Multithreaded reverse search. | * **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. |
| |
You can test your build by running the testsuite: | You can test your build by running the testsuite: |
</code> | </code> |
===== Usage ===== | ===== Usage ===== |
| 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: |
| |
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: | <code> |
| [ |
| [1,0,0], |
| [1,0,1], |
| [1,1,0], |
| [1,1,1] |
| ] |
| [ |
| [0,2,1,3], |
| [3,1,2,0], |
| [2,3,0,1] |
| ] |
| </code> |
| You can then call mptopcom in the following way: |
| |
<code> | <code> |
==== Options ==== | ==== Options ==== |
| |
- ''%%-F%%'' : Only list full/fine/spanning triangulations | - ''%%--cyclic-flips%%'' : Use special combinatorial description of the reverse search graph for cyclic polytopes |
- ''%%--flip_cache n%%'' : Sets size of flip cache to n (default: 50) | - ''%%--full%%'' : Only list full/fine/spanning triangulations |
- ''%%--make_marked_tree%%'' : Draws a tree with classes having the same node color (''%%mptopcom1%%'' only) | - ''%%--flip-cache n%%'' : Sets size of flip cache to n (default: 2000) |
- ''%%--make_tree%%'' : Will produce polymake code to plot reverse search tree (''%%mptopcom1%%'' only) | - ''%%--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) |
| - ''%%--orbit-cache n%%'' : Size of symmetry cache set to n (default: 2000) |
- ''%%--regular%%'' : Only output regular triangulations | - ''%%--regular%%'' : Only output regular triangulations |
- ''%%--orbit_cache n%%'' : Size of symmetry cache set to n (default: 50) | - ''%%--regularity-cache n%%'' : Size of regularity cache set to n (default: 2000) |
- ''%%-v%%'' : verbose (every worker will tell when he found 1000 triangulations) | - ''%%-v%%'' : verbose (every worker will tell when he found 1000 triangulations) |
| - ''%%--central%%'' : Produce only triangulations with maximal gkz[0], depends on ordering of points |
| |
==== Budgeting options ==== | ==== Budgeting options ==== |
./build/Opt/bin/mptopcom1 -v < examples/moae.dat | ./build/Opt/bin/mptopcom1 -v < examples/moae.dat |
./build/Opt/bin/mptopcom1 -v --regular < 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 --regular --full < examples/moae.dat |
./build/Opt/bin/mptopcom1 -v --flip_cache 2000 --orbit_cache 2000 < 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 | ./build/Opt/bin/mptopcom1 -v --make-tree < examples/moae.dat |
</code> | </code> |
==== mptopcom ==== | ==== mptopcom ==== |
mpirun -np 8 ./build/Opt/bin/mptopcom --regular < examples/cube_4.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 < 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 --full < 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 --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 | mpirun -np 10 ./build/Opt/bin/mptopcom < examples/lattice_3_3.dat 1>output.txt 2>error.txt |
</code> | </code> |
<HTML><li></HTML><HTML><p></HTML>Give ''%%mptopcom1%%'' an example without symmetry group:<HTML></p></HTML> | <HTML><li></HTML><HTML><p></HTML>Give ''%%mptopcom1%%'' an example without symmetry group:<HTML></p></HTML> |
<code> | <code> |
./build/Opt/bin/mptopcom1 --make_tree < mp_examples/nosym/moae.dat | ./build/Opt/bin/mptopcom1 --make-tree < mp_examples/nosym/moae.dat |
</code> | </code> |
This will just draw all nodes in the same color and the edges between them that the reverse search used.<HTML></li></HTML> | This will just draw all nodes in the same color and the edges between them that the reverse search used.<HTML></li></HTML> |
<HTML><li></HTML><HTML><p></HTML>Give ''%%mptopcom1%%'' an example with symmetry group:<HTML></p></HTML> | <HTML><li></HTML><HTML><p></HTML>Give ''%%mptopcom1%%'' an example with symmetry group:<HTML></p></HTML> |
<code> | <code> |
./build/Opt/bin/mptopcom1 --make_tree < examples/moae.dat | ./build/Opt/bin/mptopcom1 --make-tree < examples/moae.dat |
</code> | </code> |
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.<HTML></li></HTML> | 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.<HTML></li></HTML> |
<HTML><li></HTML><HTML><p></HTML>Give ''%%mptopcom1%%'' an example with symmetry group and the parameter --make_marked_tree:<HTML></p></HTML> | <HTML><li></HTML><HTML><p></HTML>Give ''%%mptopcom1%%'' an example with symmetry group and the parameter --make-marked-tree:<HTML></p></HTML> |
<code> | <code> |
./build/Opt/bin/mptopcom1 --make_marked_tree < examples/moae.dat | ./build/Opt/bin/mptopcom1 --make-marked-tree < examples/moae.dat |
</code> | </code> |
<HTML><p></HTML>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.<HTML></p></HTML><HTML></li></HTML><HTML></ol></HTML> | <HTML><p></HTML>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.<HTML></p></HTML><HTML></li></HTML><HTML></ol></HTML> |