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 `>')
along with the output. Commands and output are displayed in typewriter type.
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
Simplicity is a boolean property. So the answer is either "yes" or "no". SIMPLE says that P
is, in fact, simple. The negation would be indicated as !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
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
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.
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 cdd's (or
lrs's) 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
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.
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.
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 !SIMPLICIAL
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:
> check_iso KM3.poly cube.poly [fixing partition] (2 4)(3 5)(8 10)(11 12) level 3: 10 orbits; 2 fixed; index 2 (1 2)(5 6)(9 10)(12 13) level 2: 6 orbits; 1 fixed; index 3 (0 1)(2 3)(4 5)(6 7)(9 13) 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)(8 10)(11 12) level 3: 10 orbits; 2 fixed; index 2 (1 2)(5 6)(9 10)(12 13) level 2: 6 orbits; 1 fixed; index 3 (0 1)(2 3)(4 5)(6 7)(9 13) 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-2 3-3 4-4 5-5 6-6 7-7 8-8 9-9 10-10 11-11 12-12 13-13
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 second to last line telling us that both polytopes are, in fact, isomorphic. The last line describes the isomorphism: In this case the corresponding vertices are listed in the same order.
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 INEQUALITY
description. It looks slightly different if you solved that linear optimization problem before.
> polymake -vv linear_program.poly VOLUME polymake version 1.5.1 polymake: reading rules from ... polymake: applying rule 'cdd, VERTICES, POINTED, FEASIBLE : FACETS | INEQUALITIES, may read(AFFINE_HULL | EQUATIONS)' polymake: applying rule 'BOUNDED : VERTICES | POINTS' polymake: applying rule 'beneath_beyond, FACETS, AFFINE_HULL, VERTICES_IN_FACETS, DUAL_GRAPH, TRIANGULATION, ESSENTIALLY_GENERIC : VERTICES' polymake: applying rule 'VOLUME : BOUNDED, 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 cdd 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 cdd's 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.
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.
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
By default polymake uses the rational (exact) arithmetic provided by GNU MP. However, polymake offers an alternative rule base in order to allow the use of floating point arithmetic. This can be specified by an additional argument in the polymake call, e.g.
polymake -f float.rules dodecahedron.poly SIMPLE
This can be used to trade accuracy for execution time. 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.