This tutorial tries to give the user a first idea about polymake's features. We take a look at a variety of small examples. The text contains commands to be given to the polymake system (preceded by a '&gt') along with the output. Commands and output are displayed in typewriter type. There is an separate tutorial for using polymake to analyze rigidity of bar-and-joint frameworks.

A very simple example: the 3-cube

Suppose you have a finite set of points in some vector space Rd. Their convex hull is a polytope P. Now you want to know how many facets P has. As an example let the set S consist of the points (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1) in R3. Clearly, S is the set of vertices of a cube. Produce a text file cube.poly containing the following information.

POINTS 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1

We have the keyword POINTS followed by eight lines, where each line contains the coordinates of one point. The coordinates are preceded by an additional 1 in the first column; the reason will be discussed later. The solution of the initial problem can now be performed by polymake as follows (and, additionally, we want to know whether P is simple, that is, whether each vertex is contained in d facets, if d=dim P).

> polymake cube.poly N_FACETS SIMPLE

While polymake is searching for the answer, let us recall what polymake has to do in order to obtain the solution. It has to compute the convex hull of the given point set in terms of an explicit list of the facet describing inequalities. Then they have to be counted, which is, of course, the easy part. Nonetheless, polymake decides on its own what has to be done, before the final - admittedly trivial - task can be performed. Checking simplicity requires to look at the vertex facet incidences. In the meantime, polymake is done. Here is the answer.

N_FACETS 6 SIMPLE 1

Simplicity is a boolean property. So the answer is either "yes" or "no", encoded as 1 or 0. SIMPLE 1 says that P is, in fact, simple.

Depending on the individual configuration polymake chooses one of the convex hull computing algorithms that have a polymake interface. In the previous example polymake might have used the double description method from cddlib silently. It is also possible to specify explicitly which method to use.

As a matter of fact, polymake knows a bit about standard constructions of certain polytopes. So you will never actually have to type in your 3-cube example. You can use the following command instead. The trailing 0 indicates a cube with 0/1-coordinates.

> cube cube.poly 3 0

Visualizing a random polytope

random 3-polytope

But let us try something else. How does a typical polytope look like which is the convex hull of 20 randomly distributed points on the unit sphere in R3? This requires one command to produce a polymake description of such a polytope and a second one to launch the visualization. Again there is an implicit convex hull computation. But this time it is also necessary to determine the full combinatorial information: It has to be known which vertex is contained in which facet.

> rand_sphere random.poly 3 20 > polymake random.poly VISUAL

polymake's standard tool for visualization is JavaView, which is fully interactive. For instance, it allows you to rotate or zoom into your polytope. Here's a snapshot.

Linear programming

Polytopes most naturally appear as sets of feasible solutions of linear programs. Consider the following example.

Maximize x1 + x2 + x3 subject to x1, x2, x3 >= 0 x1, x2, x3 <= 1 x1 + x2 + x3 <= 5/2 x1 - 17x2 <= 8

In polymake's syntax this could be phrased as below. Note that we do not decide beforehand, whether we want to minimize or maximize.

LINEAR_OBJECTIVE 0 1 1 1 INEQUALITIES 0 1 0 0 0 0 1 0 0 0 0 1 1 -1 0 0 1 0 -1 0 1 0 0 -1 5/2 -1 -1 -1 8 -1 17 0

People working in optimization usually prefer other file formats (such as CPLEX's LP file format), where it is also possible to keep the names of the variables. polymake is aware of this. LP format files can be converted to polymake format. The variable names are kept, but polymake does not use them.

polytope of LP problem

It is not difficult to determine the polytope forming the solution space. Assume the file linear_program.poly contains the description given above.

> polymake linear_program.poly MAXIMAL_VALUE MAXIMAL_VALUE 5/2

This is the kind of behavior one would expect from a linear solver. Of course, usually it is also interesting to obtain a point attaining the maximum. And, in fact, polymake calls cddlib (or lrslib) Simplex code.

With polymake you can go one step further. It visualizes for you the polytope with directed edges.

> polymake linear_program.poly "VISUAL->DIRECTED_GRAPH->VERTEX_COLORS"

This is a variant of the JavaView interface. In addition to the polytope itself, the edges (whose orientation is induced by the given linear objective funtion) are drawn as arrows.

It is the essential feature of polymake that it is possible to define a polytope in one of the two equivalent ways: either as the convex hull of a set of points or as the intersection of half-spaces. If you are asking for a specific property of the polytope defined, the syntax of the call to polymake does not depend on the definition. This is entirely transparent for the user.

Triangulations

Maybe you want to know the volume of a polytope, say the truncated cube from the linear programming example above.

> polymake linear_program.poly VOLUME VOLUME 47/48

It is easy to derive the volume of a polytope from any triangulation. polymake's built-in convex hull algorithm (beneath-and-beyond) produces a (placing) triangulation as a by-product. This is used in the example above. Of course, it is possible to get the actual triangulation and to study its combinatorics. You can even visualize triangulations of 3- and 4-dimensional polytopes via the JavaView interface.

Polytopes from the combinatorial point of view

Suppose now you are not interested in a particular coordinate representation of a polytope. But instead you want to focus on the combinatorial properties only. polymake supports this point of view, too. You can specify a polytope in terms of its vertex-facet-incidence matrix. For each facet you have a line with a list of the vertices contained in that facet. The vertices are specified by numbers. They are numbered consecutively starting from 0. In each row the vertices are listed in ascending order. The following is a valid polymake description of a square.

VERTICES_IN_FACETS {0 1} {1 2} {2 3} {0 3}

Note that in this situation polymake assumes that you actually specified a polytope in this way. polymake has (almost) no means to check this.

The dimension of a polytope, i.e. the dimension of its convex hull, is an intrinsic property. It does not depend on the coordinate representation. The vertex-facet-incidence matrix suffices for polymake to compute the dimension. Assume the data above was stored in a file named square.poly.

> polymake square.poly DIM DIM 2

Sometimes one wants to construct new polytopes from old ones. Suppose we need a prism over a triangle. This can be constructed as the wedge of a square over an arbitrary facet (e.g. the first facet, which is numbered 0). This is a simple polytope, but it is not simplicial. The program option -noc (no-coordinates) limits the produced output to the pure combinatorial description.

> wedge prism.poly square.poly 0 -noc > polymake prism.poly SIMPLE SIMPLICIAL SIMPLE 1 SIMPLICIAL 0

Isomorphism checking

This section describes a feature which depends on nauty.

Suppose the file KM3.poly contains a facet description of the 3-dimensional Klee-Minty cube:

FACETS 0 1 0 0 1 -1 0 0 0 -1/4 1 0 1 -1/4 -1 0 0 0 -1/4 1 1 0 -1/4 -1

If you now want to verify that the polytope defined this way is combinatorially equivalent to the 3-dimensional 0/1-cube as produced from our client cube, then you can call check_iso:

> polymake -v check_iso KM3.poly cube.poly [fixing partition] (2 6)(3 7)(10 13)(11 12) level 3: 10 orbits; 3 fixed; index 2 (1 3)(5 6)(8 10)(9 11) level 2: 6 orbits; 1 fixed; index 3 (0 1)(2 3)(4 5)(6 7)(8 9) level 1: 2 orbits; 0 fixed; index 8 2 orbits; grpsize=48; 3 gens; 10 nodes; maxlev=4 tctotal=20; canupdates=1; cpu time = 0.00 seconds [fixing partition] (2 4)(3 5)(10 12)(11 13) level 3: 10 orbits; 2 fixed; index 2 (1 2)(5 6)(8 10)(9 11) level 2: 6 orbits; 1 fixed; index 3 (0 1)(2 3)(4 5)(6 7)(8 9) level 1: 2 orbits; 0 fixed; index 8 2 orbits; grpsize=48; 3 gens; 10 nodes; maxlev=4 tctotal=20; canupdates=1; cpu time = 0.00 seconds h and h' are identical. 0-0 1-1 2-3 3-2 4-7 5-6 6-5 7-4 8-9 9-8 10-11 11-10 12-12 13-13 check_iso 1

What you see is output for a nauty computation which gives you some information about the orbit structure of the automorphism groups of the polytopes involved. Essential is the fourth to last line telling us that both polytopes are, in fact, combinatorially equivalent. The third to last line describes the isomorphism: In this particular case the corresponding vertices (numbered 0 to 7) and the corresponding facets (numbered 8 to 13) are listed in the same order. The final two lines,

check_iso
1

with "1" meaning "true", is polymake's answer to your question. If you omit the -v flag this would be the only output given.

A more detailed look

Let us come back to the volume computation example. We want to know what polymake actually did in order to obtain the result. Specifying the -vv flag in the polymake call asks for (very) verbose information. We omit a couple of lines at the beginning of the output, where polymake tells about its rule base.

The output below corresponds to computing the VOLUME directly from the INEQUALITIES description. It looks slightly different if you solved that linear optimization problem before.

> polymake -vv linear_program.poly VOLUME polymake: reading rules from ... polymake: minimum weight rule chain constructed in 0.1 sec. polymake: applying rule cdd.convex_hull.dual: VERTICES, POINTED, FEASIBLE : FACETS | INEQUALITIES polymake: applying rule BOUNDED : VERTICES | POINTS polymake: applying rule PRECONDITION: BOUNDED ( default.volume: VOLUME : VERTICES, TRIANGULATION ) polymake: applying rule beneath_beyond.convex_hull.primal, default.triangulation: ↵ FACETS, AFFINE_HULL, VERTICES_IN_FACETS, DUAL_GRAPH, TRIANGULATION, ESSENTIALLY_GENERIC : VERTICES polymake: applying rule default.volume: VOLUME : VERTICES, TRIANGULATION VOLUME 47/48

The program which finally produces the volume is ver simple-minded: It takes any triangulation and adds up the volumes of the simplices. But before that, polymake does the following: From the rule base, the system infers that it should first call cddlib in order to obtain the vertices from the inequalities via a (dual) convex hull computation. Then it checks whether the input polyhedron is bounded, that is, to check whether the volume is finite; otherwise polymake would abort the computation. As a third step polymake constructs a triangulation, which, in fact, is obtained from calling a second convex hull code, which differs from external.cddlibs double description (or Fourier-Motzkin) method in that it additionally produces a triangulation.

An important feature of polymake is that all intermediate data which are computed are stored into the polytope file. Asking polymake a second time for the same thing, or, for something else which had been computed before, gives an immediate answer. The result is read from the file.

> polymake -vv linear_program.poly N_FACETS polymake: reading rules from ... polymake: composing a minimum weight rule chain... spent 0 sec. polymake: applying rule 'N_FACETS : FACETS' N_FACETS 7

polymake employs a special transaction model in order to assert the consistency of the polytope data. It relies on its rule base in the sense that rules whose execution terminates properly are expected to produce valid output. Moreover, polymake has a powerful error recovery mechanism which automatically looks for an alternative way to find the answer to a user's question in case of the failure of some external program.

More pictures

24-cell

Visualization of polytopes is not restricted to 3 dimensions. In particular, polymake provides data for 4-dimensional visualization. The 24-cell is a regular self-dual 4-polytope with 24 vertices. Its 24 facets are regular octahedra. The usual way to visualize a 4-dimensional polytope is by means of Schlegel diagrams. Our primary 4-D backend is again JavaView. On the right there is a picture.

graph of s3xs3

Going beyond 4 dimensions is, of course, possible but its use is limited. One way of doing this is by visualizing the graph. This makes sense for simple polytopes, in particular, since their combinatorial structure is determined by their graph due to a theorem of Blind and Mani. polymake implements a 3D-spring embedder in order to visualize the graph of an arbitrary polytope. See left for the graph of the product of two 3-simplices, that is, a 6-dimensional polytope.

> simplex s3.poly 3 > product s3xs3.poly s3.poly s3.poly > polymake s3xs3.poly VISUAL_GRAPH

A remark on the arithmetic used

By default polymake uses the rational (exact) arithmetic provided by GMP. However, polymake offers an alternative rule set which uses floating point arithmetic. It trades accuracy for execution time. To enable this, you must manually change the object type stored in the file to FloatPolytope.

Note that the combinatorial structure that is deduced from a floating point computation does not necessarily correspond to a polytope. Therefore a combinatorial examination by polymake which is based on floating point data might fail entirely. We do not plan to remedy the situation other than by exact computations. This is also the reason why the floating-point rules are never applied automatically but only after the user's manual intervention.