workshops:workshop0311-material

This page contains material used during the polymake Workshop.

Simple Computations With Polytopes

There are numerous standard constructions of polytopes. To have something computed means to ask for a (polytope's) property. Visualization is triggered via calling user_methods like VISUAL or SCHLEGEL. Syntactically these also look like properties. Convex hull (and other) computations are implicit.

$c=cube(3);
print $c->FACETS;
print_constraints($c);
print $c->F_VECTOR;
$c_polar=polarize($c);
print $c_polar->F_VECTOR;
$c_polar->VISUAL;
product(n_gon(5),n_gon(7))->SCHLEGEL(FACET=>1,EdgeColor=>"blue");

Rule Based Computation

New properties are derived from known ones via rules. The status of an object (here a permutahedron) is described via the set of properties known. Asking for a new property forces polymake to compute a sequence of rules (forming a schedule) which are then applied to the object. Usually, this is automatic. However, it is possible to inspect what is going on before any actual computation takes place.

$p=permutahedron(3);
print join(", ", $p->list_properties);
$schedule=$p->get_schedule("SIMPLE");
print join("\n", $schedule->list);
$schedule->apply($p);
print join(", ", $p->list_properties);
print $p->SIMPLE;

Getting Help

The online help uses text placed near the respective implementations.

help 'objects';
help 'objects/Polytope';
$t=typeof $c;
print join(", ", sorted_uniq(sort { $a cmp $b } map { keys %{$_->properties} } $t, @{$t->super}));

Long Integer Arithmetic

The exact integer (and rational) arithmetic is based on the GMP:

$f = new Integer(1);
for ($i = new Integer(100); $i>0; --$i) { $f *= $i; }
print $f;

New: Polynomials

polymake has a new class for polynomials. This is mainly a container without much functionality. While standard operators are defined, beware that they still follow the standard Perl precedences.

$r=new Ring("x","y");
($x,$y)=$r->variables;
$p=1*(1+$x*$y)-1*($x+($y^2))+2*(($x^2)+$y);
$N=newton($p);
print $N->VERTICES;
print fac($N->DIM)*$N->VOLUME;

Perl Power

The benefit of using a standard programming language such as Perl is that one can use standard libraries for basic needs. Here is an example showing how to benchmark two different convex hull algorithms/codes on the same example.

use Benchmark qw(:all);
$r=rand_sphere(3,1000,seed=>1); $t=timeit(1,'$r->FACETS;'); print timestr($t);
$r=rand_sphere(3,1000,seed=>1); prefer_now("beneath_beyond"); $t=timeit(1,'$r->FACETS;'); print timestr($t);

This code does not work in a script file (.pl) because of polymake's modifications to Perl. You rather want to use something like this.

use Benchmark qw(:all);
use application 'polytope';

my $r=rand_sphere(3,100,seed=>1);

sub getfacets{
  $r->FACETS;
}

sub myBenchmark{
  my $t=Benchmark::timeit(1,"getfacets"); 
  print timestr($t);
}

Other Kinds of Objects

polymake's object/rule concept is not restricted to polytopes. Here are a few example computations with finite simplicial complexes,

application 'topaz';
$rp2=projective_plane();
print $rp2->HOMOLOGY;
print $rp2->CONNECTED;
print rows_labeled($rp2->HOMOLOGY);
$t=torus();
print $t->FACETS;
$t->VISUAL;

The entire script used for the introduction presentation: gen.script

BEG

The example extension created during the tutorial: example.zip

The demo file used for the new application Foo: foo.demo

Objects Are Immutable

application "polytope";
$p=new Polytope<Rational>(POINTS=>cube(3)->VERTICES/new Vector<Rational>([1,2,2,2]));
print $p->VERTICES;

Objects Are Equivalence Classes

$p=new Polytope<Rational>(POINTS=>[[1,0],[1,1]]);
print $p->VOLUME;
$q=new Polytope<Rational>(INEQUALITIES=>$p->FACETS);
print equal_polyhedra($p,$q);
print $p->VERTICES_IN_FACETS;
$r=new Polytope<Rational>(VERTICES_IN_FACETS=>$p->VERTICES_IN_FACETS);
print $r->VOLUME;
print equal_polyhedra($p,$r);
print isomorphic($p,$r);

Take It to Extremes

@fs = map { 8 } 1..24;
$g=new Graph(BIPARTITE=>1);
$s=new Polytope<Rational>(COMBINATORIAL_DIM=>4, FACET_SIZES=>\@fs, GRAPH=>$g);
print $s->CUBICAL;

Users Are Responsible

$t=new Polytope<Rational>(COMBINATORIAL_DIM=>3,N_VERTICES=>2);
$t=new Polytope<Rational>(N_VERTICES=>-5);
print $t->N_VERTICES;
check_poly(cube(3)->VERTICES_IN_FACETS,verbose=>1);

Polytope Is Dervived From Cone

$c=cube(3);
print $c->VERTICES;
print $c->CONE_DIM, " ", $c->CONE_AMBIENT_DIM;
print $c->DIM, " ", $c->AMBIENT_DIM;

Unbounded Polyhedra

$q=new Polytope<Rational>(INEQUALITIES=>$c->FACETS->minor(~[$c->N_FACETS-1],All));
print $q->BOUNDED;
print $q->FAR_FACE, " ", $q->N_VERTICES;
print $q->VERTICES_IN_FACETS;
$q2=orthantify($q);
print $q2->POSITIVE;
$q3=bound($q2);
print $q3->BOUNDED;
print isomorphic($q,$q3);
$q3->VISUAL;

Non-trivial Lineality Space

$q=new Polytope<Rational>(INEQUALITIES=>$c->FACETS->minor(~[4..5],All));
print $q->N_VERTICES;
print $q->VERTICES_IN_FACETS;
print $q->F_VECTOR;

In the visual tutorial we will take a tour through the visualization opportunities given by polymake. You can try it on your own using the command file vis.demo and the supplementary file vis.zip containing two polytope files and one polymake script.

Polytope visualization

Every visualization tutorial starts with a cube – this one doesn't. We prefer truncated octahedra.

prefer 'jreality';
$oct = cross(3);
$oct_trunc = truncation($oct,All);
$oct_trunc->VISUAL;

Visualizing the truncation

Now we compose the octahedron with the truncated octahedron to understand what exactly happened.

compose($oct->VISUAL,$oct_trunc->VISUAL);
compose($oct->VISUAL(FacetStyle=>"hidden",VertexStyle=>"hidden"),$oct_trunc->VISUAL);
$oct_trunc->VISUAL->TRIANGULATION;

Visualizing lattice points

The truncated cross polytope only contains one lattice point, but after scaling it by a factor of two it contains more. The color of the lattice points indicates whether the points lie on a facet or strictly in the interior.

$oct_trunc->VISUAL->LATTICE;
$T = new Matrix<Rational>([ [1/2, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]);
$oct_scaled = new Polytope<Rational>(VERTICES => ($oct_trunc->VERTICES)*$T);
$oct_scaled->VISUAL->LATTICE_COLORED;

Visualizing in higher dimensions

A simple visualization of the graph of the truncated 4-cross polytope using our spring embedder.

$cr4 = cross(4);
$cr4_trunc = truncation($cr4,All);
$cr4_trunc->VISUAL_GRAPH;

Visualizing with linear objective

We select one of the facets corresponding to a cut off vertex and make the defining inequality the linear objective of a linear program. The VERTEX_COLORS indicate the value of the objective function at the vertices. But we can even set the vertex labels to the proper value using a small perl subroutine.

print $cr4_trunc->VERTICES_IN_FACETS;
print rows_numbered($cr4_trunc->VERTICES_IN_FACETS);
$lp = new LinearProgram<Rational>(LINEAR_OBJECTIVE=>${$cr4_trunc->FACETS}[16]);
$cr4_trunc->LP = $lp;
$cr4_trunc->VISUAL_GRAPH->VERTEX_COLORS;
$l = $lp->LINEAR_OBJECTIVE;
$cr4_trunc->VISUAL_GRAPH(NodeLabels=> sub { my $i = shift; my $v = ${$cr4_trunc->VERTICES}[$i]; my $val = $l*$v; return $val;} )->VERTEX_COLORS;

Changing face colors

We use a small subroutine to color a soccerball in a traditional way or to create a terribly colored disco-ball.

$soccerball = load("soccerball.poly");
$soccerball->VISUAL(FacetColor => sub { $i = shift; $s = ${$soccerball->VERTICES_IN_FACETS}[$i]; if($s->size == 5) { return "black"; } else { return "white"; } });
rand_sphere(3,100)->VISUAL(FacetColor => sub { return new RGB(rand,rand,rand); }, VertexColor => sub { return new RGB(rand,rand,rand); }, EdgeStyle => "hidden");

Schlegel diagrams

The Schlegel diagram is the projection of a polytope onto one of its faces. The zoom factor determines the distance of the center of projection from the projection facet. In dimension 3 we may visualize the entire construction and illustrate the influence of the zoom factor. In dimension 4 it is possible to add all the 3 dimensional facets to the Schlegel diagram.

$cr4_trunc->SCHLEGEL(ZOOM=>".6");
$oct_trunc->SCHLEGEL(ZOOM=>".5")->CONSTRUCTION;
compose($oct_trunc->SCHLEGEL(ZOOM=>".5",EdgeColor=>"orange")->CONSTRUCTION, $oct_trunc->SCHLEGEL(ZOOM=>".7")->CONSTRUCTION);
$cr4_trunc->SCHLEGEL(ZOOM=>".5")->SOLID(FacetTransparency=>".9");

Tight spans

The tight span is an unbounded polyhedron associated with a finite metric space. In our case the metric is generated by some genes of bees. The resulting tight span is high dimensional, but we can visualize its graph with edge colors hinting at the dimension of the faces the edges are contained in.

$ts = load("bees.poly");
$ts->VISUAL_BOUNDED_GRAPH->EDGE_COLORS;

Tropical polytopes

We can also visualize tropical polytopes and hypersurfaces.

application 'tropical';
$tcyc = cyclic(3,5);
$tcyc->VISUAL_PSEUDOVERTEX_GRAPH;
$ths = new Hypersurface(MONOMIALS=>[[1,1,2,1],[0,1,3,1],[0,3,2,0],[1,2,1,1]],COEFFICIENTS=>[1,3,2,2]);
$ths->VISUAL;

Fans

The normal fan consists of all normal cones at the vertices of a polytope. A little script properly visualizes the normal cones at the vertices of the polytope.

application 'fan';
$nf = normal_fan($oct_trunc);
$nf->VISUAL;
script("visual_normal_fan",$oct_trunc);

The documented PRL-tutorial. All examples in one file:
prl.script points.demo

  • workshops/workshop0311-material.txt
  • Last modified: 2019/01/29 21:46
  • by 127.0.0.1