engleski

polyhedral: A GAP package for dual description and group homology

A polytope can be described alternatively as the convex hull of its finite set of vertices or as the intersection of its finite set of facet defining inequalities. The process of obtaining one description from the other is named dual description problem and is an essential step in many algorithms. We propose here some methods for computing such dual description in the cases where the polytope is highly symmetric. For a given polyhedral cone C in Rn given by N generating rays v_i one can define three possible symmetry groups: (i) Combinatorial symmetry group Comb(C): this is the group of transformations f of Sym(N) preserving the set of faces of P globally. (ii) Projective symmetry group Proj(C): this is the group of transformations f of Sym(N) such that there exist alpha_i>0$, A in GL_n(R) with A v_i=alpha_i v_{; ; f(i)}; ; . (iii) Linear symmetry group Lin(C): this is the group of transformations f of Sym(N) such that there exist A in GL_n(R) with A v_i=v_{; ; f(i)}; ; . The key method for computing dual description up to symmetry is the adjacency decomposition method. It allows an optimal use of the existing symmetries and allowed the solution of several famous problems. It is based on existing software for polyhedral computations (cdd, lrs), on nauty for graph computation and GAP for group theoretic computations. Running the adjacency decomposition method implies computing the set of facets adjacent to a given facet. This computation is precisely a dual description computation and so we may apply the adjacency decomposition method recursively when this becomes too complicated. The problem is that the number of cases may grow too fast. We used three methods for dealing with this problem: (i) One is to connectivity results like Balinski theorem to prove that we do not need to go any further in the computation. (ii) Another is to use a banking system to store known dual descriptions and check in advance before computing one. (iii) Another is to use the specific symmetry group of a face, which might be larger than the stabilizer of the face. We will also report implementation details. The problem of enumeration of vertices can be generalized to infinite settings, i.e. polyhedral tesselations, Delaunay polytopes, etc. We expose the case of the Ryshkov polyhedra Ryshkov(n), which is the cone of n x n- matrices having minimum at least 1. The vertices of this cone are called perfect form and are related to lattice sphere packings. By using the Ryshkov polyhedra Ryshkov(n) one gets an approximate classifying space for the general linear group GL_n(Z). By using resolutions of finite group, one can make build a free resolution for the group PSL_4(Z) and this allows us to compute H_k(PSL_4(Z), Z) for $k<=5.

polytope; recursive adjacency decomposition; Ryshkov polyhedra

nije evidentirano