mpha is a software developed at TU Berlin for computing chambers induced by a hyperplane arrangement in parallel. It is a combination of

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

Please read this very carefully! mpha 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 3.2 installed. In particular, you need the polymake callable library, which might not be installed by the package manager of your distribution.

Installation can be done with the following three commands:

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


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.

  • mpha1: Runs reverse search single threaded.
  • mpha: Multithreaded reverse search.

You can test your build by running the testsuite:


Input files are formatted as in polymake. You can just use

$HA = new HyperplaneArrangement(...);

in polymake to generate a valid input file for mpha. You can then call mpha in the following way:

mpirun -np 5 mpha --input some_name.hyar

If you did not run make install you can call the binary in the build/Opt/bin folder:

mpirun -np 5 ./build/Opt/bin/mpha --input some_name.hyar

There are several options you can invoke to modify the behaviour of mpha:

  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 mpha1 and mpha using the above options. It is assumed that mpha was build, but not installed and that the current directory is the root of the source directory.

./build/Opt/bin/mpha1 --input square.hyar
mpirun -np 8 ./build/Opt/bin/mpha --input square.hyar

The following is an example for checkpointing and restarting:

mpirun -np 8 ./build/Opt/bin/mpha -v -stop stop_file -checkp checkp_file --input square.hyar
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/mpha -v -restart checkp_file --input square.hyar

mpha1 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 mpha1 an example without symmetry group:
./build/Opt/bin/mpha1 --make-tree --input square.hyar

This will just draw all nodes in the same color and the edges between them that the reverse search used. 2. Give mpha1 an example with symmetry group:

./build/Opt/bin/mpha1 --make-tree --input square.hyar

mpha is joint work of the following two authors:

mpha and polymake are licensed under the GNU General Public License version 2.

See the files COPYING and LICENSE in the source for further details.

  • mpha.txt
  • Last modified: 2020/11/03 10:16
  • by lkastner