Polymake - Polymake

Polymake
Logo Polymake.png
Polymake screenshot.png
Původní autořiEwgenij Gawrilow a Michael Joswig
První vydání1989; Před 31 lety (1989)
Stabilní uvolnění
3.4 / 15. dubna 2019; Před 19 měsíci (2019-04-15)
Úložiště
Upravte to na Wikidata
NapsánoC ++, Perl
Operační systémLinux, Mac
K dispozici vAngličtina
LicenceGNU General Public License
webová stránkapolymake.org

Polymake je software pro algoritmické léčba konvexní mnohostěn.[1]

Ačkoli primárně nástrojem ke studiu kombinatorika a geometrie konvexní polytopes a mnohostěn, je nyní také schopen se vypořádat s zjednodušené komplexy, matroidy, mnohostěnní fanoušci, grafy, tropický předměty, torické odrůdy a další předměty.

Polymake byl citován ve více než 100 posledních článcích indexovaných podle Zentralblatt MATH jak je patrné z jeho záznamu v databázi swMATH.[2]

Speciální funkce

modulární

Polymake byl původně navržen jako výzkumný nástroj pro studium aspektů polytopů.[3] Jako takový používá polymake mnoho softwarových balíčků třetích stran pro specializované výpočty, čímž poskytuje společné rozhraní a most mezi různými nástroji. Uživatel může snadno (a nevědomky) přepínat mezi použitím různých softwarových balíčků v procesu výpočtu vlastností mnohostěnu.[4]

výpočet založený na pravidlech

Polymake interně používá model server-klient, kde server uchovává informace o každém objektu (např. Mnohostěn) a klienti odesílají požadavky na výpočet vlastností. Úkolem serveru je určit, jak pomocí systému založeného na pravidlech dokončit každý požadavek z již známých informací o každém objektu.[5] Například existuje mnoho pravidel, jak vypočítat aspekty mnohostěnu. Fazety lze vypočítat z popisu vrcholů mnohostěnů a z (možná redundantního) popisu nerovností. Polymake vytváří graf závislostí popisující kroky ke zpracování každého požadavku a vybere nejlepší cestu pomocí algoritmu typu Dijkstra.[5]

skriptování

Polymake lze použít v rámci perl skriptu. Kromě toho mohou uživatelé rozšířit polymake a definovat nové objekty, vlastnosti, pravidla pro výpočetní vlastnosti a algoritmy.[6]

Polymake aplikace

Polymake rozděluje svou sbírku funkcí a objektů do 10 různých skupin zvaných aplikace. Chovají se jako jmenné prostory C ++. Polytopová aplikace byla první vyvinutou a je největší.[7]

Běžná aplikace

Tato aplikace obsahuje mnoho „pomocných“ funkcí používaných v jiných aplikacích.[8]

Aplikace ventilátoru

Aplikace Fan obsahuje funkce pro mnohostěnné komplexy (které se zobecňují zjednodušené komplexy ), rovinné kresby 3-polytopů, mnohostěnní fanoušci a dělení bodů nebo vektorů.[9]

Aplikace Fulton

Tato aplikace se zabývá normální torické odrůdy. Název této aplikace je z knihy „Úvod do torických odrůd“ od autora William Fulton.[10]

Grafová aplikace

Grafová aplikace slouží k manipulaci s směrovanými a neorientovanými grafy. Některé standardní funkce grafu existují (například pro sousedství a kliky) spolu s kombinatorickými funkcemi, jako je výpočet mřížky představované směrovaným acyklickým grafem.[11]

Skupinová aplikace

Skupinová aplikace se zaměřuje na konečné permutační skupiny. Základní vlastnosti skupiny lze vypočítat jako postavy a hodiny konjugace.[12] V kombinaci s polytopem může tato aplikace vypočítat vlastnosti spojené se skupinou působící na polytop permutací vrcholů, fazet nebo souřadnic polytopu.

Ideální aplikace

Ideální aplikace počítá několik vlastností polynomiálních ideálů: Gröbnerův základ, Hilbertův polynom a radikály.[13]

Matroid aplikace

Třída matroidů může vypočítat všechny standardní vlastnosti matroidu, jako jsou základy a obvody. Tato aplikace může také vypočítat pokročilejší vlastnosti, jako je Tutteův polynom matroidu a realizace matroidu s polytopem.[14]

Aplikace Polytop

V rámci aplikace polytop existuje více než 230 funkcí nebo výpočtů, které lze provést s polytopem. Tyto funkce se pohybují od složitosti od jednoduchého výpočtu základních informací o mnohostěnu (např. Počet vrcholů, počet fazet, testy jednoduchých polytopů a převod popisu vrcholu na popis nerovnosti) až po kombinatorické nebo algebraické vlastnosti (např. H-vektor, Ehrhartův polynom, Hilbertův základ, a Schlegel diagramy ).[7] Existuje také mnoho možností vizualizace.

Aplikace Topaz

Aplikace Topaz obsahuje všechny související funkce abstraktní zjednodušené komplexy.[15] Lze provést mnoho pokročilých topologických výpočtů nad zjednodušenými komplexy homologické skupiny, orientace, základní skupina. K dispozici je také kombinatorická kolekce vlastností, které lze vypočítat jako a ostřelování a Hasse diagramy.

Tropická aplikace

Tropická aplikace obsahuje funkce pro zkoumání tropické geometrie; zejména tropické hyperplochy a tropické kužely.[16]

Historie vývoje

Polymake verze 1.0 se poprvé objevil ve sborníku Mezinárodního kongresu matematiků v roce 1989 v nové sekci o matematickém softwaru.[17] Verze 1.0 obsahovala pouze polytopovou aplikaci, ale systém „aplikací“ ještě nebyl vyvinut. Verze 2.0 byla vydána někdy v roce 2003,[Citace je zapotřebí ] a verze 3.0 byla vydána v roce 2016.[18]

Softwarové balíčky

Používá se v rámci polymake

Níže je uveden seznam softwarových balíčků třetích stran, se kterými může polymake komunikovat od verze 3.0. Uživatelé také mohou psát nové soubory pravidel pro propojení s libovolným softwarovým balíčkem. Všimněte si, že v tomto seznamu je určitá redundance (např. Pro nalezení konvexního trupu mnohostěnu lze použít několik různých balíčků). Protože polymake používá pro výpočetní vlastnosti soubory pravidel a graf závislostí,[6] většina z těchto softwarových balíčků je volitelná. Některé se však stávají nezbytnými pro specializované výpočty.

  • 4ti2: softwarový balíček pro algebraické, geometrické a kombinatorické úlohy v lineárních prostorech
  • odstín: teorie tropických křižovatek
  • azove: výčet vrcholů 0/1
  • CDD: metoda dvojího popisu pro převod mezi nerovnostním a vrcholným popisem mnohostěnu
  • Geomview: interaktivní 3D prohlížecí program
  • Gfan: Gröbner fanoušci a tropické odrůdy
  • GraphViz: software pro vizualizaci grafů
  • LattE (Výčet mřížových bodů): počítání mřížových bodů uvnitř polytopů a integrace přes polytopy
  • libnormalizovat: afinní monoidy, vektorové konfigurace, mřížkové polytopy a racionální kužele
  • lrs: implementace algoritmu zpětného vyhledávání pro výčet vrcholů a konvexní obal problémy
  • nauty: automorfismus skupiny grafů
  • permlib: nastavení stabilizátoru a výpočtů na oběžné dráze
  • PORTA: výčet mřížových bodů mnohostěnu
  • ppl: Parma Polyhedra Library
  • qhull: Quickhull algoritmus pro konvexní trupy
  • jednotné číslo: počítačový algebraický systém pro polynomiální výpočty se zvláštním důrazem na komutativní a nekomutativní algebru, algebraickou geometrii a teorii singularity
  • skica: pro vytváření perokresby dvou- nebo trojrozměrných objemových objektů
  • RozdělitStrom4: fylogenetické sítě
  • sympol: nástroj pro práci se symetrickým mnohostěnem
  • tři: Knihovna JavaScript pro animovanou 3D počítačovou grafiku
  • tikz: TeXové balíčky pro programové vytváření grafiky
  • TOPCOM: triangulace bodových konfigurací a matroidů
  • TropLi: pro výpočet tropických lineárních prostorů matroidů
  • tosimplex: Duální simplexní algoritmus implementovaný Thomasem Opferem
  • Vinci: objemy polytopů

Používá se ve spojení s polymake

Reference

  1. ^ Oficiální webové stránky
  2. ^ „Polymake - Matematický software - swMATH“.
  3. ^ Gawrilow, Ewgenij; Joswig, Michael (01.01.2000). Kalai, Gil; Ziegler, Günter M. (eds.). polymake: rámec pro analýzu konvexních polytopů. Polytopes — kombinatorika a výpočet, seminář DMV. Birkhäuser Basilej. 43–73. doi:10.1007/978-3-0348-8438-9_2. ISBN  9783764363512.
  4. ^ Gawrilow, Ewgenij; Joswig, Michael (01.01.2001). Polymake: Přístup k modulárnímu softwarovému designu ve výpočetní geometrii. Sborník ze sedmnáctého výročního symposia o výpočetní geometrii. SCG '01. New York, NY, USA: ACM. str. 222–231. doi:10.1145/378583.378673. ISBN  978-1581133578. S2CID  16519425.
  5. ^ A b Gawrilow, Ewgenij; Joswig, Michael (2005-07-13). Msgstr "Geometrické uvažování s polymake". arXiv:matematika / 0507273.
  6. ^ A b Joswig, Michael; Müller, Benjamin; Paffenholz, Andreas (2009-02-17). "Polymake a Lattice Polytopes". arXiv:0902.2919 [math.CO ].
  7. ^ A b "dokumentace polymake, aplikace: polytope". polymake.org. Citováno 2016-06-11.
  8. ^ "dokumentace polymake, aplikace: společná". polymake.org. Citováno 2016-06-11.
  9. ^ "dokumentace polymake, aplikace: fan". polymake.org. Citováno 2016-06-11.
  10. ^ "dokumentace polymake, aplikace: fulton". polymake.org. Citováno 2016-06-11.
  11. ^ "dokumentace polymake, aplikace: graf". polymake.org. Citováno 2016-06-11.
  12. ^ "dokumentace polymake, aplikace: skupina". polymake.org. Citováno 2016-06-11.
  13. ^ "dokumentace polymake, aplikace: ideální". polymake.org. Citováno 2016-06-11.
  14. ^ "dokumentace polymake, aplikace: matroid". polymake.org. Citováno 2016-06-11.
  15. ^ "dokumentace polymake, aplikace: topaz". polymake.org. Citováno 2016-06-11.
  16. ^ "dokumentace polymake, aplikace: tropické". polymake.org. Citováno 2016-06-11.
  17. ^ Joswig, Michael; Gawrilow, Ewgenij (1998). „Polymake“. Sborník příspěvků z mezinárodního kongresu matematiků.
  18. ^ „Polymake 3.0“. GitHub. Citováno 2016-06-28.