user_guide:tutorials:face_lattice_tutorial

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
tutorial:face_lattice_tutorial [2012/09/18 20:25] – [Dealing with Large Polytopes] gawrilowuser_guide:tutorials:face_lattice_tutorial [2019/02/04 22:55] (current) – external edit 127.0.0.1
Line 1: Line 1:
-====== Face lattices (of Polytopes) ======+{{page>.:latest:@FILEID@}}
  
-By definition the face lattice of a polytope contains all the combinatorial information about a polytope.  Here we want to explore how to work with this in polymake.  Let's start simple. 
- 
-<code> 
-polytope > $p = n_gon(5); 
-polytope > $HD = $p->HASSE_DIAGRAM;        
-polytope > print $HD->FACES; 
-{} 
-{0} 
-{1} 
-{2} 
-{3} 
-{4} 
-{1 2} 
-{2 3} 
-{3 4} 
-{0 4} 
-{0 1} 
-{0 1 2 3 4} 
-</code> 
- 
-The obvious question is: How to interpret that output?  Well, the Hasse diagram of a partially ordered set is implemented as a special kind of a directed graph.  Hence all operations on (directed) graphs work.  Each node of the Hasse diagram represents a face.  One way to give a name to such a face is to list all the vertices contained, and this is the output above.  A key feature is that the faces come sorted by dimension. 
- 
-Very often just a part of the face lattice is interesting.  The following command lists just the 1-dimensional faces. 
-<code> 
-polytope > for (my $k=$HD->DIMS->[1]; $k<$HD->DIMS->[2]; ++$k) { print $HD->FACES->[$k] } 
-{1 2}{2 3}{3 4}{0 4}{0 1} 
-</code> 
-The above works as described since DIMS return an array with the first nodes of each dimension. 
- 
-Face lattices of polytopes can be huge.  So it may be an advantage to compute only a part.  The following computes the 2-skeleton of an 8-dimensional cube. 
-<code> 
-polytope > $c=cube(8); 
-polytope > $HD_partial = hasse_diagram($c->VERTICES_IN_FACETS,2); 
-polytope > print $HD_partial->DIMS; 
-1 257 1281 3073 
-</code> 
-Instead of listing all those thousands of faces here we give only the vector of starting nodes.  This can be treated just like above.  The (partial) f-vector is obtained by taking successive differences. 
-<code> 
-polytope > $partial_f = $HD_partial->DIMS; 
-polytope > for (my $i=1; $i<$partial_f->size(); ++$i) { print $partial_f->[$i]-$partial_f->[$i-1], " " } 
-256 1024 1792  
-</code> 
- 
-===== Dealing with Large Polytopes ===== 
- 
-In order to get the most out of the above it is important to understand that this kind of computation is a two-staged process.  In the first step, polymake determines VERTICES_IN_FACETS, that is, the combinatorial description of the polytope, and then the computation of HASSE_DIAGRAM only takes this incidence matrix as its input; no coordinates involved in the second step. 
- 
-To get at the incidence matrix typically requires a convex hull computation.  This can be triggered like this.  Intentionally, there is no output. 
-<code> 
-polytope > $p=rand_sphere(6,100);  
-polytope > $p->VERTICES_IN_FACETS; 
-</code> 
-Notice that this takes a couple of seconds with the default convex hull code (via cdd), even on a large machine; and the reason is that the double description method employed is not best possible for this kind of input.  You can speed up //this// computation as follows. 
-<code> 
-polytope > prefer_now "beneath_beyond"; $p->VERTICES_IN_FACETS; 
-</code> 
-Temporarily (that is, only in this command) we change the default convex hull code to polymake's built-in beneath-and-beyond method.  This is faster on this particular input. 
- 
-In general, there is no way to tell ahead of time which convex hull algorithm works best.  So, for your own experiments you will have to try.  To get an idea you might want to look up: 
-  * Avis, David; Bremner, David; Seidel, Raimund: How good are convex hull algorithms? 11th ACM Symposium on Computational Geometry (Vancouver, BC, 1995). Comput. Geom. 7 (1997), no. 5-6, 265–301. 
-  * Joswig, Michael: Beneath-and-beyond revisited. Algebra, geometry, and software systems, 1–21, Springer, Berlin, 2003. 
- 
-The subsequent second stage looks as above; but the difference is that VERTICES_IN_FACETS is known already. 
-<code> 
-polytope > $HD_partial = hasse_diagram($p->VERTICES_IN_FACETS,2); 
-polytope > print $HD_partial->DIMS; 
-1 101 2082 12534 
-</code> 
-The executive summary: While polymake is designed to do all kinds of things automatically, you might have to guide it a little if you are computing with large or special input. 
- 
-One more caveat:  A //d//-polytope with //n// vertices has at most //O(n^(d/2))// facets.  This is the consequence of the Upper-Bound-Theorem. 
-  * McMullen, Peter:  The maximum numbers of faces of a convex polytope. Mathematika 17 (1970) 179-184. 
-This number is actually attained by neighborly polytopes; for example, by the cyclic polytopes. 
  • user_guide/tutorials/face_lattice_tutorial.1347999930.txt.gz
  • Last modified: 2014/01/03 15:45
  • (external edit)