mptopcom

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
mptopcom [2019/05/16 12:32] – [mptopcom] Update paper lkastnermptopcom [2024/03/25 09:05] (current) – external edit 127.0.0.1
Line 13: Line 13:
 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.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.11 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.4 ==== 
 + 
 +  * gcc 11.3.0, openmpi 4.1.5, polymake 4.11 
 +  * clang 18.1.1, openmpi 4.1.5, polymake 4.11 
 + 
 +==== 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.
Line 21: Line 39:
 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.0r2.tar.bz2|mptopcom-1.0.tar.bz2]]+  * [[https://polymake.org/lib/exe/fetch.php/download/mptopcom-1.4.tar.bz2|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. 
 + 
 +==== Old versions ==== 
 + 
 +  * [[https://polymake.org/lib/exe/fetch.php/download/mptopcom-1.3.tar.bz2|mptopcom-1.3.tar.bz2]] from 2022-09-01. 
 +  * [[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_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.0r2.tar.bz2|mptopcom-1.0r2.tar.bz2]] from 2018-05-14 with a bugfix for newer polymake.
  
 ===== Installation ===== ===== Installation =====
Line 32: Line 60:
 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
  
Line 37: Line 66:
 ./configure --help ./configure --help
 </code> </code>
 +
 The most important options are The most important options are
  
Line 44: Line 74:
 --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 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 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.   * **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.
 +  * **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:
Line 56: Line 90:
 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 =====
  
-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:+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: 
 + 
 +<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>
 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:
  
Line 68: Line 136:
 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.
  
Line 74: Line 143:
 ==== 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 ====
  
-  - ''%%-maxnodes%%'' only affects the "bumpsat maxnodes and scale*maxnodes. +  - ''%%-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) +  - ''%%-scale%%'' sets the scaling factor when we have many jobs available (workers can work longer if we arent 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)+  - ''%%-maxd%%'' sets the max depth to go to when we dont 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)   - ''%%-lmax%%'' sets the point where -scale is used (if |L| > lmax * numproc)
   - ''%%-lmin%%'' sets the point where -maxd is used (if |L| < lmin * numproc)   - ''%%-lmin%%'' sets the point where -maxd is used (if |L| < lmin * numproc)
Line 96: Line 168:
 ===== Sample usage ===== ===== 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.+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.
  
 ==== mptopcom1 ==== ==== mptopcom1 ====
Line 105: Line 177:
 ./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 -< 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 ====
  
Line 116: Line 189:
 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 -< 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 ---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>
 +
 The following is an example for checkpointing and restarting: The following is an example for checkpointing and restarting:
  
Line 126: Line 200:
 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
  
Line 131: Line 206:
 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 =====
  
 ''%%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: ''%%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:
  
-<HTML><ol style="list-style-type: decimal;"></HTML> +  - Give ''%%mptopcom1%%'' an example without symmetry group: 
-<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> + 
-<HTML><li></HTML><HTML><p></HTML>Give ''%%mptopcom1%%'' an example with symmetry group:<HTML></p></HTML>+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: 
 <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> + 
-<HTML><li></HTML><HTML><p></HTML>Give ''%%mptopcom1%%'' an example with symmetry group and the parameter --make_marked_tree:<HTML></p></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. 3. Give ''%%mptopcom1%%'' an example with symmetry group and the parameter –make-marked-tree: 
 <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>+ 
 +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 ===== ===== Authors =====
Line 156: Line 235:
 **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 AlgorithmicsHokkaido University, Japan +  * **[[https://www.otaru-uc.ac.jp/~skip/|Skip Jordan]]**, Department of Information and Management ScienceOtaru 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 
-  * **[[http://page.math.tu-berlin.de/~kastner/|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 =====
Line 169: Line 253:
  
 See the files ''%%COPYING%%'' and ''%%LICENSE%%'' in the source for further details. See the files ''%%COPYING%%'' and ''%%LICENSE%%'' in the source for further details.
- 
  
  • mptopcom.1558009965.txt.gz
  • Last modified: 2019/05/16 12:32
  • by lkastner