Wikipedia

Polymake

Software

Polymake (Eigenschreibweise polymake) ist eine Software zur algorithmischen Behandlung von konvexen Polytopen und Polyedern.[1]

Polymake

Polymake logo
Basisdaten

Hauptentwickler Ewgenij Gawrilow und Michael Joswig
Erscheinungsjahr 1997
Aktuelle Version 4.11
(6. November 2023)
Betriebssystem Linux, Mac
Programmier­sprache C++, Perl
Lizenz GNU General Public License
Polymake.org

Zunächst konzipiert als Mittel zur Untersuchung der Kombinatorik und Geometrie von konvexen Polytopen und Polyedern[2], ist Polymake nun in der Lage, Berechnungen mit simplizialen Komplexen, Matroiden, Kegeln, Graphen, tropischen Objekten, Torischen Varietäten und weiteren Objekten durchzuführen. Besonders die Berechnungen von konvexen Hüllen und Gitterpunkten eines Polytops sind von besonderer Bedeutung für verschiedenste anderweitige Forschung.[3]

Polymake wurde in über 300 Artikeln, die beim Zentralblatt MATH registriert sind, zitiert, wie man dem Eintrag in der swMATH-Datenbank entnehmen kann.[4]

Besonderheiten und Aufbau

Bearbeiten

Polymake weist ein paar Besonderheiten auf, die es von anderer Software unterscheidet.

Zunächst kann Polymake als Teil eines Perl-Skriptes aufgerufen werden. Dazu können Benutzer Polymake um neue Objekte, Eigenschaften, Regeln und Algorithmen erweitern.[5]

Außerdem weist es ein internes Client-Server-Modell auf, wobei die Sprache Perl für das Objekt-Management und die Schnittstellen und C++ für die Algorithmik gebraucht wird.[6] Der Server speichert Informationen über das Objekt, z. B. ein Polytop, und der Client sendet Anfragen um bestimmte Eigenschaften zu bestimmen. Der Server hat die Aufgabe zu bestimmen, wie jede Anfrage auf Grundlage von bereits bekannten Informationen zu jedem Objekt mithilfe eines regelbasierten Systems abgeschlossen wird. Zum Beispiel gibt es viele Regeln, wie man die Facetten eines Polytops bestimmt. Diese können aus einer Eckenbeschreibung des Polytops und aus einer (möglicherweise redundanten) Ungleichungsbeschreibung berechnet werden. Polymake erstellt einen Abhängigkeitsgraphen, der die Schritte zur Bearbeitung jeder Anfrage modelliert, und wählt den besten Pfad mithilfe eines Dijkstra-Algorithmus aus.[6]

Polymake unterteilt seine Funktionen und Objekte in 10 verschiedene Gruppen, sogenannte applications. Sie verhalten sich ähnlich wie Namensräume in C++. Die application "polytop" ist die größte und die erste, die entwickelt wurde.[7]

  • Common: Hilfsfunktionen, die in anderen applications vorkommen.[8]
  • Graph: Manipulation von gerichteten und unterrichteten Graphen.[11]
  • Group: Berechnungen primär für endliche Permutationsgruppen. Grundlegende Eigenschaften einer Gruppe wie die Charaktere und Konjugationsklassen können auch bestimmt werden.[12]
  • Matroid: Berechnung von Standardeigenschaften eines Matroiden wie Basen und Kreisen. Diese application kann auch tieferliegende Eigenschaften wie das Tutte-Polynom eines Matroids berechnen und das Matroid mit einem Polytop realisieren.[14]
  • Polytope: Hier befinden sich mehr als 230 Funktionen oder Berechnungen, die mit einem Polytop durchgeführt werden können. Diese Funktionen variieren in ihrer Komplexität, angefangen bei einfachen Berechnungen grundlegender Eigenschaften eines Polytop (z. B. Anzahl der Ecken, Anzahl der Facetten, Tests für simpliziale Polytope und Umwandlung einer Eckenbeschreibung in eine Ungleichungsbeschreibung) bis hin zu kombinatorischen oder algebraischen Eigenschaften (z. B. H-Vektoren, Ehrhartpolynome, Hilbertbasen, und Schlegeldiagramme).[15] Es gibt auch viele Möglichkeiten sich Berechnungen visuell auszugeben.
  • Topaz: Funktionen, die sich mit simplizialen Komplexen beschäftigen.[16] Viele aufwändige Berechnungen wie die der Homologiegruppe, der Orientierung und der Fundamentalgruppe von simplizialen Komplexen können durchgeführt werden. Außerdem können einige kombinatorische Eigenschaften wie das Hasse-Diagramm oder das sogenannte shelling bestimmt werden.

Entwicklungsgeschichte

Bearbeiten

Die Polymake-Version 1.0 erschien erstmals in den Proceedings des DMV-Seminars "Polytopes and Optimization" in Oberwolfach im November 1997.[18] Damals enthielt sie nur die polytope-application, wobei der Aufbau anhand von applications noch nicht angefertigt war. Die Versionen 2.0 und 3.0 wurde im Juli 2003 und 2016 veröffentlicht.[19][20] Die neueste große Update kam mit Version 4.0 und wurde im Januar 2020 herausgegeben.[21]

Zusammenspiel mit anderer Software

Bearbeiten

Polymake weist einen besonders modularen Aufbau auf und besitzt daher viele Schnittstellen mit anderen Softwarepaketen, die für bestimmte Berechnungen spezialisiert sind, wodurch es auch als Schnittstellen zwischen diesen verschiedenen Tools fungieren kann. Ein Benutzer kann problemlos, teils ohne dessen bewusst zu sein, zwischen der Verwendung verschiedener Softwarepakete wechseln, während die Eigenschaften eines Polytops berechnet werden.[22]

Pakete, die in Polymake enthalten sind

Bearbeiten

Im Folgenden werden einige externe Softwarepakete angegeben, mit denen Polymake, beim Stand der Version 4.0, interagieren kann. Es ist aber jederzeit möglich Schnittstellen für anderweitige Software durch eigens geschriebene Regeldateien zu erstellen. Einige Pakete werden sehr ähnliche Berechnungen durchführen, z. B. gibt es verschiedene Pakete zum Bestimmen der konvexen Hülle eines Polytops. Da Polymake Regeldateien und einen Abhängigkeitsgraphen für die Berechnung von solchen Eigenschaften verwendet,[23] sind die meisten dieser Softwarepakete optional. Einige sind jedoch für spezialisierte Berechnungen erforderlich.

  • 4ti2:Softwarepaket für algebraische, geometrische und kombinatorische Rechnungen auf linearen Räumen
  • a-tint: Algorithmische Methoden für Tropische Schnitttheorie
  • azove: Aufzählung von 0/1 Ecken
  • barvinok: Zählen von ganzzahligen Punkten von parametrisierten und nichtparametrisierten Polytopen
  • cdd: Sogenannte "double description method" zum Wechseln zwischen einer Eckenbeschreibung und Ungleichungsbeschreibung eines Polytops.
  • Geomview: Interaktives 3D-Visualisierungsprogramm
  • Gfan: Gröbnerfächer und tropische Varietäten
  • GraphViz: Software zur Visualisierung von Graphen
  • homology: Berechnung von Homologiegruppen von simplizialen Komplexen
  • LattE (Lattice point Enumeration): Zählen von Gitterpunkten in einem Polytop und Integration darüber
  • libnormaliz: Affine Monoide, Vektorkonfigurationen, Gitterpolytope und rationale Kegel
  • lrs: Implementierung des Reverse-Search Algorithmus für Fragestellung zum Aufzählen der Ecken und der Berechnung der konvexen Hülle eines Polytops
  • mptopcom: Berechnung von Triangulierungen von Punktkonfigurationen und Matroiden mithilfe einer parallelen Rückwärtssuche
  • nauty: Automorphismengruppen von Graphen
  • plantri: Planare Triangulierungen
  • permlib: Berechnungen von Stabilisatoren und Orbits durch Permutationsgruppen
  • PORTA: Aufzählen von Gitterpunkten eines Polytops
  • ppl: Parma Polyhedra Library
  • qhull: Quickhull-Algorithmus für konvexe Hüllen
  • singular: Computeralgebrasystem für Rechnungen in Polynomringen mit besonderem Schwerpunkt auf kommutativer und nichtkommutativer Algebra, algebraischer Geometrie und Singularitätstheorie.
  • sketch: Zum Zeichnen von 2- oder 3-dimensionalen festen Objekten
  • SplitsTree4: Phylogenetische Netzwerke
  • sympol: Zum Rechnen mit symmetrischen Polyedern
  • threejs: JavaScript-Bibliothek für 3D-Computeranimationen
  • tikz: TeX-Paket zum Programmieren von Grafiken
  • TropLi: Berechnen von tropischen linearen Räumen von Matroiden
  • tosimplex: Dualer Simplexalgorithmus von Thomas Opfer implementiert
  • Vinci: Volumina von Polytopen

Zusammen mit Polymake in Verwendung

Bearbeiten

Einzelnachweise

Bearbeiten
  1. ↑ Polymake wiki. In: Polymake.org. Abgerufen am 14. November 2023 (englisch).
  2. ↑ Ewgenij Gawrilow, Michael Joswig: Polymake: a Framework for Analyzing Convex Polytopes. In: Polytopes — Combinatorics and Computation. Birkhäuser Basel, Basel 2000, ISBN 978-3-7643-6351-2, S. 43–73, doi:10.1007/978-3-0348-8438-9_2 (springer.com [abgerufen am 15. November 2023]).
  3. ↑ Benjamin Assarf, Ewgenij Gawrilow, Katrin Herr, Michael Joswig, Benjamin Lorenz, Andreas Paffenholz, Thomas Rehn: Computing convex hulls and counting integer points with Polymake. In: Mathematical Programming Computation. Band 9, Nr. 1, März 2017, ISSN 1867-2949, S. 1–38, doi:10.1007/s12532-016-0104-z (springer.com [abgerufen am 15. November 2023]).
  4. ↑ Software Search - zbMATH Open. Abgerufen am 15. November 2023.
  5. ↑ Michael Joswig, Benjamin Müller, Andreas Paffenholz: Polymake and Lattice Polytopes. 17. Februar 2009, arxiv:0902.2919 [math.CO].
  6. ↑ a b Ewgenij Gawrilow, Michael Joswig: Geometric Reasoning with Polymake. 13. Juli 2005, arxiv:math.CO/0507273.
  7. ↑ application polytope. In: Polymake wiki. Abgerufen am 15. November 2023 (englisch).
  8. ↑ application common. In: Polymake wiki. Abgerufen am 15. November 2023.
  9. ↑ application fan. In: Polymake wiki. Abgerufen am 15. November 2023.
  10. ↑ application fulton. In: Polymake wiki. Abgerufen am 15. November 2023.
  11. ↑ application graph. In: Polymake wiki. Abgerufen am 15. November 2023.
  12. ↑ application group. In: Polymake wiki. Abgerufen am 15. November 2023.
  13. ↑ application ideal. In: Polymake wiki. Abgerufen am 15. November 2023.
  14. ↑ application matroid. In: Polymake wiki. Abgerufen am 15. November 2023.
  15. ↑ application polytope. In: Polymake wiki. Abgerufen am 15. November 2023 (englisch).
  16. ↑ application topaz. In: Polymake wiki. Abgerufen am 15. November 2023 (englisch).
  17. ↑ application tropical. In: Polymake wiki. Abgerufen am 15. November 2023 (englisch).
  18. ↑ Ewgenij Gawrilow, Michael Joswig: Polymake: a Framework for Analyzing Convex Polytopes. In: Polytopes — Combinatorics and Computation. Birkhäuser Basel, Basel 2000, ISBN 978-3-7643-6351-2, S. 43–73, doi:10.1007/978-3-0348-8438-9_2 (springer.com [abgerufen am 15. November 2023]).
  19. ↑ release of Polymake 2.0. Abgerufen am 15. November 2023.
  20. ↑ === Polymake 3.0 === · Polymake/Polymake@146d79b. Abgerufen am 15. November 2023 (englisch).
  21. ↑ Polymake 4.0. In: Polymake wiki. Abgerufen am 15. November 2023.
  22. ↑ Ewgenij Gawrilow, Michael Joswig: Polymake: an approach to modular software design in computational geometry. ACM, 2001, ISBN 978-1-58113-357-8, S. 222–231, doi:10.1145/378583.378673 (acm.org [abgerufen am 15. November 2023]).
  23. ↑ Michael Joswig, Benjamin Müller, Andreas Paffenholz: Polymake and Lattice Polytopes. 17. Februar 2009, arxiv:0902.2919 [math.CO].
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Polymake&oldid=241032923“