Naslov
Polyhedral: A GAP package for polytope and lattice computations using symmetries

Autori
Dutour Sikirić, Mathieu

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, pp prezentacija, znanstveni

Izvornik
Mini-Workshop: Exploiting Symmetry in Optimization / - , 2010

Skup
Mini-Workshop: Exploiting Symmetry in Optimization

Mjesto i datum
Oberwolfach, Njemačka, 23.08.2010. - 27.08.2010

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
polytope ; dual description ; adjacency method

Sažetak
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 {; ; \em dual description problem}; ; and is an essential step in many algorithms. We consider here the method for such computation that uses symmetry in their methodology. The key such method is the computation of the set of orbits by the adjacency decomposition method. It allows an optimal use of the existing symmetries and allowed the solution of several famous problems. A key step in applying it is the existing software for symmetry computations. One part is the GAP package that contains procedure for backtracking and another is nauty that allows the computation of automorphism group of graphs and thus of polytopes. We indicate how the method can be applied recursively and how the key ingredient for its success are the use of Balanski theorem and of banking system. This framework of the adjacency decomposition method can be applied to several other problems: the enumeration of perfect forms, perfect domain, and Delaunay tesselations. The program polyhedral can also compute with face- lattices, flag systems and compute volume of polytope. Besides its polytopal features, it can also enumerate sublattices in lattices and also embeddings of polytopes.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA