external_software

External Software Overview

By far not every feature of polymake system is developed by the polymake project team itself. Instead, we purposely rely on the expertise of various research groups in the community. It is one of the main goals of our project to increase the interoperability of all the fascinating publicly available geometric software. And last but not least, having quite constrained woman-power and time resources, it is obviously much easier to interface a well-tested, ready-to-use software package than to implement everything from scratch.

The external software used in polymake can be divided in three categories:

The following libraries are mandatory prerequisites for polymake. You can't build nor use polymake without having them installed on your system.

• GNU Multiple-Precision Library (GMP) (version at least 5.1)

A well-known implementation of integer, rational, and floating-point arithmetic (and beyond) with unlimited precision. It became a standard arithmetic engine in many geometric and algebraic software packages in the last years. polymake makes massive use of the GMP integers and rationals via own C++ wrapper classes.

• GNU Multiple-Precision floating-point computations with correct Rounding (MPFR) (version 3.X)

Floating-point arithmetic with predictable and platform-independent results. Used in polymake for some constructions requiring intermediate floating-point computations, like random sphere or regular n-gon.

• boost headers are required for the permlib interface and the bundled extension libnormaliz, see below.

The following are polymake extensions that are included in the main package and provide interfaces to important external software. Some include the source code of the librarys they interface, others come as bare interfaces to software that you have to install seperately.

Note: The -minimal archive of polymake excludes the bundled code but still has the interfaces for cdd, libnormaliz, lrs and nauty. Furthermore, the bundled extension for jreality is removed.

Shipped with polymake

These libraries are packed together with the polymake distribution, thanks to license agreements and/or kind allowance of the authors. You don't have to download and install them separately. We are keeping track of their further development and always include the most recent versions available at the moment of making the current polymake release.

• cdd: Convex hull computations
Provides an interface to cddlib (by Komei Fukuda, Institute for Operations Research, ETH Zürich).
Note: This interface can also work with an installed version instead of the bundled code.

Contains the double description method (dual Fourier-Motzkin) for convex hull and vertex enumeration, as well as a dual simplex LP solver, both implemented for floating-point and unlimited precision rational numbers.

• jreality: Provides an interface to jReality (by Charles Gunn, Tim Hoffmann, Markus Schmies, Steffen Weissmann et al., Geometry Group, TU Berlin).
Needs ant to be built.

High-end visualization in 3D (experimental). A stable snapshot of jReality source code is bundled with polymake. You don't need to download it separately unless you will try a most recent version of it.

• libnormaliz: Computations with affine monoids.
Provides an interface to Normaliz (by Winfried Bruns, Bogdan Ichim and Christof Söger).
Note: This interface can also work with an installed version instead of the bundled code.

Normaliz is a tool for computations in affine monoids, vector configurations, lattice polytopes, and rational cones. Since version 2.8 it comes with a very fast parallelized algorithm for lattice point enumeration.

• lrs: Convex hull computations
Provides an interface to lrslib (by David Avis, McGill University).
Note: This interface can also work with an installed version instead of the bundled code.

Contains the reverse search method of Avis and Fukuda, and a primal simplex LP solver, both using unlimited precision arithmetic.

• nauty: Computing of automorphism groups of graphs
Provides an interface to nauty (version 2.5r9)
by Brendan McKay, Australian National University.
Note: This interface can also work with a custom source directory instead of the bundled code, since 3.0r2.
Alternative: bliss

Computes automorphism groups of graphs. polymake uses it for checking combinatorial equivalence and congruence of polytopes as well as isomorphy of graphs.

• sympol: Dealing with symmetric polytopes
Provides an interface to SymPol (by Thomas Rehn and Achill Schürmann).

Bare interfaces

polymake provides interfaces to the software listed here, but does not ship the software itself. You have to install it yourself and configure polymake to use your installation. See the instructions on configuration for help with this.

• bliss: Computing of automorphism groups of graphs
Provides an interface to bliss (by Tommi Junttila and Petteri Kaski).
Requires headers to be installed in a subfolder bliss in the include directory, as in the debian package.
Alternative: nauty

• flint: Fast Library for Number Theory
Provides an interface to FLINT (by William Hart).
Used for fast univariate polynomial arithmetic and number theory.

• javaview: Provides an interface to JavaView (by Konrad Polthier, Felix Kälberer, Samy Khadem, Eike Preuss, Ulrich Reitebuch, Sonderforschungsbereich 288, TU Berlin).

Visualizes 3D- and 4D-polytopes (and much more).

• ppl: a modern C++ library for the manipulation of numerical information that can be represented by points in some n-dimensional vector space
Provides an interface to the Parma Polyhedra Library (by Roberto Bagnara et al)

• singular: Working with Gröbner bases
Provides an interface to Singular (by Wolfram Decker, Gert-Martin Greuel, Gerhard Pfister, and Hans Schönemann).
Please check the installation details for the bundled extension singular.

• scip: Provides an interface to SCIP by the developers from the Zuse Institute Berlin (ZIB)

SCIP is a solver for Mixed Integer Linear and Nonlinear Problems that allows for an easy integration of arbitrary constraints.

Note: Please build SCIP with -DGMP=true and -DZIMPL=false. The latter is necessary due to a symbol conflict with libcdd.

• soplex: SoPlex is an optimization package for solving linear programming problems (LPs) based on an advanced implementation of the primal and dual revised simplex algorithm.
Provides an interface to SoPlex (by Roland Wunderling, Ambros Gleixner, Matthias Miltenberger, Benjamin Müller and others).
Please build SoPlex with GMP=true and SHARED=true.

In order to use the following software from within polymake, you need download and install the packages on your own, provided you accept the license agreements. Don't merge them into the polymake directory tree, as they might get overwritten by the next polymake upgrade.

They can then be enabled or disabled in a running polymake session with reconfigure “something.rules”;. The auto-configuration routines try to find the installed software (usually by examining your PATH variable). See here for help.

We provide bundeled extensions for jReality and JavaView, see the above section. Other interfaces to visualization software:

• geomview
Geometry Center, University of Minnesota.

Visualizes 3D- and 4D-polytopes.

• Visualizes graphs and face lattices.

• 3D- and 4D-visualization by high-end ray-tracing.

• SplitsTree
by David Bryant and Daniel Huson, Universität Tübingen.

Visualization of phylogenetic trees.

• three.js
by Ricardo Cabello.

three.js is a lightweight 3D library with a very low level of complexity. Provides 3D-visualization in a webbrowser.

• 4ti2
by Ralf Hemmecke, Raymond Hemmecke, Matthias Köppe, Peter Malkin, and Matthias Walter.

A software package for algebraic, geometric and combinatorial problems on linear spaces.

• azove (version 2.0)
by Markus Behle.
Linux RPM available

azove is a tool designed for counting (without explicit enumeration) and enumeration of 0/1 vertices. Given a polytope by a linear relaxation or facet description P = {x | Ax ⇐ b}, all 0/1 points lying in P can be counted or enumerated. This is done by intersecting the polytope P with the unit-hypercube [0,1]d. The integral vertices (no fractional ones) of this intersection will be enumerated. If P is a 0/1 polytope, azove solves the vertex enumeration problem.

Note: azove2 might not run on systems with a low percentage of free memory (change LEFTOVER_FREE_MEMORY in azove.cpp) and also under linux kernel ≥3.14 due to changes in /proc/meminfo. This patch removes the dynamic memory allocation, forces a fixed number of signature nodes and thus works around the problems on recent kernel versions.

• barvinok
by Sven Verdoolaege.

barvinok is a library for counting the number of integer points in parametrized and non-parametrized polytopes. For parametrized polytopes an explicit function in the shape of a piece-wise step-polynomial is constructed. This is a generalization of both Ehrhart quasi-polynomials and vector partition functions.

Rule files using barvinok for the computation of the number of lattice points and the coefficients of the Ehrhart polynomial are currently not part of the standard polymake distribution. They are available as a separate extension to polymake.

• Gfan
by Anders Nedergaard Jensen, Aarhus Universitet.

Gfan is a software package for computing Gröbner fans and tropical varieties.

• homology
by Jean-Guillaume Dumas, Frank Heckenbach, B. David Saunders and Volkmar Welker.

An efficient program computing homology groups of simplicial complexes.

• LattE
by Jesus De Loera and his co-authors.

LattE is a software dedicated to the problems of counting and detecting lattice points inside convex polytopes, and the solution of integer programs. LattE contains the first ever implementation of Barvinok's algorithm. LattE stands for “Lattice point Enumeration”. We recommend to use LattE macchiato instead, the improved and enhanced version of LattE by Matthias Köppe.

• LattE macchiato is an improved version of LattE, derived from the latest release 1.2. For full functionality either choose the version “LattE, for tea, too”, that also installs 4ti2 and other required packages or first install TOPCOM, NTL, LiDia, and 4ti2.

• mptopcom is a software developed at TU Berlin and Hokkaido University for computing triangulations of point configurations in parallel.

• PORTA (version 1.3.2)
by Thomas Christoph and Andreas Loebel, ZIB / Universität Heidelberg.

An implementation of Fourier-Motzkin elimination. This program seems not to be further developed nor maintained any more; moreover, the limited precision arithmetic used in it makes it fail in ways hard to predict or analyze. This is why its use is heavily deprecated. We offer an interface mostly for historical reasons.

If you must use it nonetheless at the very least increase the length of the char arrays fname and outfname in porta.c, say from 20 to 255, in order to avoid some segfaults.

See also the function porta2poly for importing PORTA files into polymake.

• Qhull computes the convex hull, Delaunay triangulation, Voronoi diagram, halfspace intersection about a point, furthest-site Delaunay triangulation, and furthest-site Voronoi diagram.

• TOPCOM (version 0.16.0)
by Jörg Rambau, Universität Bayreuth.

Explores triangulations of points configurations.

• vinci (version 1.0.5)
by Benno Büeler, Andreas Enge, and Komei Fukuda.

Computes the volume of polytopes using floating point arithmetic.

Note: Version numbers given in the descriptions are not binding. These are the latest versions that we are aware of and proven to work with polymake. You are free to use other versions as long as the backward compatibility (API and/or interchange file format, whatever appropriate) is preserved.

• external_software.txt