Polymake Explained

Polymake
Author:	Ewgenij Gawrilow and Michael Joswig
Programming Language:	C++, Perl
Operating System:	Linux, Mac
Language:	English
License:	GNU General Public License

polymake is a software for the algorithmic treatment of convex polyhedra.^[1]

Albeit primarily a tool to study the combinatorics and the geometry of convex polytopes and polyhedra,^[2] it is by now also capable of dealing with simplicial complexes, matroids, polyhedral fans, graphs, tropical objects, toric varieties and other objects. In particular, its capability to compute the convex hull and lattice points of a polytope proved itself to be quite useful for different kinds of research.^[3]

polymake has been cited in over 300 recent articles indexed by Zentralblatt MATH as can be seen from its entry in the swMATH database.^[4]

Special features and applications

polymake exhibits a few particularities, making it special to work with.

Firstly, polymake can be used within a Perl script. Moreover, users can extend polymake and define new objects, properties, rules for computing properties, and algorithms.^[5]

Secondly, it exhibits an internal client-server scheme to accommodate the usage of Perl for object management and interfaces as well as C++ for mathematical algorithms.^[6] The server holds information about each object (e.g., a polytope), and the client sends requests to compute properties. The server has the job of determining how to complete each request from information already known about each object using a rule-based system. For example, there are many rules on how to compute the facets of a polytope. Facets can be computed from a vertex description of the polytope, and from a (possibly redundant) inequality description. polymake builds a dependency graph outlining the steps to process each request and selects the best path via a Dijkstra-type algorithm.

polymake divides its collection of functions and objects into 10 different groups called applications. They behave like C++ namespaces. The polytope application was the first one developed and it is the largest.^[7]

• Common: "helper" functions used in other applications.^[8]
• Fan: functions for polyhedral complexes (which generalize simplicial complexes), planar drawings of 3-polytopes, polyhedral fans, and subdivisions of points or vectors.^[9]
• Fulton: computations with normal toric varieties. It is named after William Fulton, author "Introduction to Toric Varieties".^[10]
• Graph: manipulation of directed and undirected graphs.^[11]
• Group: focus on finite permutation groups. Basic properties of a group can be calculated like characters and conjugacy classes.^[12]
• Ideal: computations on polynomial ideals: Gröbner basis, Hilbert polynomial, and radicals.^[13]
• Matroid: computation of standard properties of a matroid, like bases and circuits. This application can also compute more advanced properties like the Tutte polynomial of a matroid and realizing the matroid with a polytope.^[14]
• Polytope: over 230 functions or calculations that can be done with a polytope. These functions range in complexity from simply calculating basic information about a polytope (e.g., number of vertices, number of facets, tests for simplicial polytopes, and converting a vertex description to an inequality description) to combinatorial or algebraic properties (e.g., H-vector, Ehrhart polynomial, Hilbert basis, and Schlegel diagrams). There are also many visualization options.
• Topaz: functions relating to abstract simplicial complexes.^[15] Many advanced topological calculations over simplicial complexes can be performed like homology groups, orientation and fundamental group. There is also a combinatorial collection of properties that can be computed, like a shelling and Hasse diagrams.
• Tropical: functions for exploring tropical geometry; in particular, tropical hypersurfaces and tropical cones.^[16]

Development History

polymake version 1.0 first appeared in the proceedings of DMV-Seminar "Polytopes and Optimization" held in Oberwolfach, November 1997. Version 1.0 only contained the polytope application, but the system of "applications" was not yet developed. Version 2.0 was in July 2003, ^[17] and version 3.0 was released in 2016.^[18] The last big revision, version 4.0, was released in January 2020.^[19]

Interaction with other software packages

polymake is highly modularly built and, therefore, displays great interaction with third party software packages for specialized computations, thereby providing a common interface and bridge between different tools. A user can easily (and unknowingly) switch between using different software packages in the process of computing properties of a polytope.^[20]

Used within polymake

Below is a list of third-party software packages that polymake can interface with as of version 4.0. Users are also able to write new rule files for interfacing with any software package. Note that there is some redundancy in this list (e.g., a few different packages can be used for finding the convex hull of a polytope). Because polymake uses rule files and a dependency graph for computing properties, most of these software packages are optional. However, some become necessary for specialized computations.

• 4ti2: software package for algebraic, geometric and combinatorial problems on linear spaces
• a-tint: tropical intersection theory
• azove: enumeration of 0/1 vertices
• barvinok: counting of integer points in parametrized and non-parametrized polytopes
• cdd: double description method for converting between an inequality and vertex description of a polytope
• Geomview: interactive 3D viewing program
• Gfan: Gröbner fans and tropical varieties
• GraphViz: graph visualization software
• homology: computation homology groups of simplicial complexes
• LattE (Lattice point Enumeration): counting lattice points inside polytopes and integration over polytopes
• libnormaliz: affine monoids, vector configurations, lattice polytopes, and rational cones
• lrs: implementation of the reverse-search algorithm for the vertex enumeration problem and convex hull problems
• mptopcom: computation of triangulations of point configurations and matroids using parallel reverse search
• nauty: automorphism groups of graphs
  • plantri: planar triangulations permlib: set stabilizer and in-orbit computations
• PORTA: enumerate lattice points of a polytope
• ppl: Parma Polyhedra Library
• qhull: Quickhull algorithm for convex hulls
• singular: computer algebra system for polynomial computations, with special emphasis on commutative and non-commutative algebra, algebraic geometry, and singularity theory
• sketch: for making line drawings of two- or three-dimensional solid objects
• SplitsTree4: phylogenetic networks
• sympol: tool to work with symmetric polyhedra
• threejs: JavaScript library for animated 3D computer graphics
• tikz: TeX packages for creating graphics programmatically
• TropLi: for computing tropical linear spaces of matroids
• tosimplex: Dual simplex algorithm implemented by Thomas Opfer
• Vinci: volumes of polytopes

Used in conjunction with polymake

• jupyter-polymake: allows polymake within Jupyter notebooks.
• OSCAR: Open Source Computer Algebra Research system currently under development
• PolymakeInterface: package for using polymake in GAP.
• PolyViewer: GUI viewer for polymake fies.

Notes and References

1. http://polymake.org Official Website
2. Book: Gawrilow . Ewgenij . polymake: a Framework for Analyzing Convex Polytopes . Joswig . Michael . 2000-01-01 . Birkhäuser Basel . 9783764363512 . Kalai . Gil . Polytopes—combinatorics and computation, DMV Seminar . 43–73 . en . 10.1007/978-3-0348-8438-9_2 . Ziegler . Günter M..
3. Assarf . Benjamin . Gawrilow . Ewgenij . Herr . Katrin . Joswig . Michael . Lorenz . Benjamin . Paffenholz . Andreas . Rehn . Thomas . 2017-03-01 . Computing convex hulls and counting integer points with polymake . Mathematical Programming Computation . en . 9 . 1 . 1–38 . 10.1007/s12532-016-0104-z . 1867-2957. 1408.4653 . 5594262 .
4. Web site: Polymake - Mathematical software - swMATH.
5. 0902.2919 . math.CO . Michael . Joswig . Benjamin . Müller . Polymake and Lattice Polytopes . 2009-02-17 . Paffenholz . Andreas.
6. math/0507273 . Ewgenij . Gawrilow . Michael . Joswig . Geometric Reasoning with polymake . 2005-07-13.
7. Web site: polymake documentation, application: polytope. polymake.org. 2016-06-11.
8. Web site: polymake documentation, application: common. polymake.org. 2016-06-11.
9. Web site: polymake documentation, application: fan. polymake.org. 2016-06-11.
10. Web site: polymake documentation, application: fulton. polymake.org. 2016-06-11.
11. Web site: polymake documentation, application: graph. polymake.org. 2016-06-11.
12. Web site: polymake documentation, application: group. polymake.org. 2016-06-11.
13. Web site: polymake documentation, application: ideal. polymake.org. 2016-06-11.
14. Web site: polymake documentation, application: matroid. polymake.org. 2016-06-11.
15. Web site: polymake documentation, application: topaz. polymake.org. 2016-06-11.
16. Web site: polymake documentation, application: tropical. polymake.org. 2016-06-11.
17. Web site: release of polymake 2.0 . 2023-11-13 . www.computational-geometry.org.
18. Web site: Polymake 3.0. GitHub. 2016-06-28.
19. Web site: Polymake 4.0 [polymake wiki] ]. 2023-11-13 . polymake.org.
20. Book: Gawrilow . Ewgenij . Joswig . Michael . Polymake: An approach to modular software design in computational geometry . 2001-06-01 . Proceedings of the seventeenth annual symposium on Computational geometry . https://doi.org/10.1145/378583.378673 . SCG '01 . New York, NY, USA . Association for Computing Machinery . 222–231 . 10.1145/378583.378673 . 978-1-58113-357-8. 16519425 .