Both sides previous revision Previous revision Next revision | Previous revision Next revisionBoth sides next revision |
mptopcom [2022/04/11 17:20] – [Authors] schroeter | mptopcom [2023/05/13 11:04] – additional vesrion tested joswig |
---|
**mptopcom** is a software developed at TU Berlin and Hokkaido University for computing triangulations of point configurations in parallel. It is a combination of | **mptopcom** is a software developed at TU Berlin and Hokkaido University for computing triangulations of point configurations in parallel. It is a combination of |
| |
* **[[https://www.wm.uni-bayreuth.de/de/team/rambau_joerg/TOPCOM/index.html|TOPCOM]]** for triangulations, | * **[[http://www.rambau.wm.uni-bayreuth.de/TOPCOM/|TOPCOM]]** for triangulations, |
* **[[https://polymake.org/doku.php|polymake]]** for combinatorics, and | * **[[https://polymake.org/doku.php|polymake]]** for combinatorics, and |
* **[[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. |
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 4.0 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. |
| |
| **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. |
| |
| ===== Known working configurations ===== |
| |
| ==== mptopcom 1.3 ==== |
| |
| * 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 |
| |
| ==== Legacy: mptopcom-1.0 – 1.2 ==== |
| |
**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.2.tar.bz2|mptopcom-1.2.tar.bz2]] | * [[https://polymake.org/lib/exe/fetch.php/download/mptopcom-1.3.tar.bz2|mptopcom-1.3.tar.bz2]] from 2022-09-01. |
| |
Note that recent changes in polymake were breaking, so only the second version works with polymake 4.0 and newer. | **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. |
| |
==== Old versions ==== | ==== Old versions ==== |
| |
| * [[https://polymake.org/lib/exe/fetch.php/download/mptopcom-1.2.tar.bz2|mptopcom-1.2.tar.bz2]] from 2020-08-28. |
* [[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.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. | * [[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. |
ninja -C build/Opt install | ninja -C build/Opt install |
</code> | </code> |
| |
There are several options to the ''%%./configure%%'' command that can be viewed with | There are several options to the ''%%./configure%%'' command that can be viewed with |
| |
./configure --help | ./configure --help |
</code> | </code> |
| |
The most important options are | The most important options are |
| |
--prefix=/path/to/install/dir | --prefix=/path/to/install/dir |
</code> | </code> |
| |
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. |
| |
* **canonicalRepresentative**: Compute the canonical representative from the orbit of a triangulation. | * **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. | * **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: | You can test your build by running the testsuite: |
perl testsuite.pl | perl testsuite.pl |
</code> | </code> |
| |
| ==== mpirun ==== |
| |
| 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. |
| |
| ==== More than 64 points ==== |
| |
| 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 |
| |
| <code> |
| CXXFLAGS=-DWITH_PM_BITSET ./configure |
| </code> |
| |
| 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. |
| |
===== Usage ===== | ===== Usage ===== |
| |
] | ] |
</code> | </code> |
| |
You can then call mptopcom in the following way: | You can then call mptopcom in the following way: |
| |
mpirun -np 5 mptopcom < examples/cube_4.dat | mpirun -np 5 mptopcom < examples/cube_4.dat |
</code> | </code> |
| |
If you did not run ''%%make install%%'' you can call the binary in the ''%%build/Opt/bin%%'' folder: | 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 | mpirun -np 5 ./build/Opt/bin/mptopcom < examples/cube_4.dat |
</code> | </code> |
| |
This will produce all triangulations of the four dimensional cube. | This will produce all triangulations of the four dimensional cube. |
| |
./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 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> |
| |
The following is an example for checkpointing and restarting: | The following is an example for checkpointing and restarting: |
| |
touch stop_file | touch stop_file |
</code> | </code> |
| |
Now the state will be written to the file ''%%checkp_file%%'' and after a while the computation stops. Restart it with | 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 | mpirun -np 8 ./build/Opt/bin/mptopcom -v -restart checkp_file < examples/cube_4.dat |
</code> | </code> |
| |
===== Drawing the reverse search tree ===== | ===== Drawing the reverse search tree ===== |
| |
./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. 2. Give ''%%mptopcom1%%'' an example with symmetry group: | 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 | ./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. 3. Give ''%%mptopcom1%%'' an example with symmetry group and the parameter –make-marked-tree: | 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 | ./build/Opt/bin/mptopcom1 --make-marked-tree < examples/moae.dat |
</code> | </code> |
| |
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. | 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: | **mptopcom** is joint work of the following three authors: |
| |
* **[[https://www-alg.ist.hokudai.ac.jp/~skip/|Skip Jordan]]**, Laboratory for Algorithmics, Hokkaido University, Japan | * **[[https://www.otaru-uc.ac.jp/~skip/|Skip Jordan]]**, Department of Information and Management Science, Otaru University of Commerce, Japan |
* **[[http://page.math.tu-berlin.de/~joswig/|Michael Joswig]]**, Department of Mathematics, TU Berlin, Germany | * **[[https://page.math.tu-berlin.de/~joswig/|Michael Joswig]]**, Department of Mathematics, TU Berlin, Germany |
* **[[https://lkastner.github.io/|Lars Kastner]]**, Department of Mathematics, TU Berlin, Germany | * **[[https://lkastner.github.io/|Lars Kastner]]**, Department of Mathematics, TU Berlin, Germany |
| * **[[https://page.math.tu-berlin.de/~panizzut/|Marta Panizzut]]**, Department of Mathematics, TU Berlin, Germany |
| |
**mptopcom** is based on **TOPCOM** which is developed by | **mptopcom** is based on **TOPCOM** which is developed by |
| |
* **[[http://www.rambau.wm.uni-bayreuth.de/|Jörg Rambau]]**, Department of Mathematics, Universität Bayreuth, Germany | * **[[https://www.rambau.wm.uni-bayreuth.de/|Jörg Rambau]]**, Department of Mathematics, Universität Bayreuth, Germany |
| |
| ===== Acknowledgements ===== |
| |
| We are very grateful to **[[https://www.math.tu-berlin.de/fachgebiete_ag_diskalg/fg_diskrete_mathematik_geometrie/v-menue/mitarbeiter/benjamin_lorenz/v-menue/home/|Benjamin Lorenz]]** for many discussions and for lending us his C++ expertise during the implementation phase. |
| |
===== License ===== | ===== License ===== |
| |
See the files ''%%COPYING%%'' and ''%%LICENSE%%'' in the source for further details. | See the files ''%%COPYING%%'' and ''%%LICENSE%%'' in the source for further details. |
| |
| |