Полимейк
Оригинальный автор(ы)Евгений Гаврилов и Михаэль Йосвиг
Первоначальный выпуск1997 ; 28 лет назад ( 1997 )
Стабильный релиз
4.11 / 6 ноября 2023 г. ; 14 месяцев назад ( 2023-11-06 )
Репозиторий
  • github.com/polymake/polymake
Написано вС++ , Perl
Операционная системаLinux , Макинтош
Доступно вАнглийский
ЛицензияСтандартная общественная лицензия GNU
Веб-сайтpolymake.org

polymake — это программное обеспечение для алгоритмической обработки выпуклых многогранников . [1]

Хотя в первую очередь это инструмент для изучения комбинаторики и геометрии выпуклых многогранников и полиэдров , [2] он теперь также способен работать с симплициальными комплексами , матроидами , многогранными веерами, графами , тропическими объектами, торическими многообразиями и другими объектами. В частности, его способность вычислять выпуклую оболочку и точки решетки многогранника оказалась весьма полезной для различных видов исследований. [3]

polymake цитировался в более чем 300 недавних статьях, проиндексированных Zentralblatt MATH, как видно из его записи в базе данных swMATH. [4]

Специальные функции и приложения

polymake обладает рядом особенностей, делающих работу с ним особенно приятной.

Во-первых, polymake может использоваться в скрипте Perl . Более того, пользователи могут расширять polymake и определять новые объекты, свойства, правила для вычисления свойств и алгоритмы. [5]

Во-вторых, он демонстрирует внутреннюю схему клиент-сервер для размещения использования Perl для управления объектами и интерфейсами, а также C++ для математических алгоритмов. [6] Сервер хранит информацию о каждом объекте (например, политопе), а клиент отправляет запросы для вычисления свойств. Сервер имеет задачу определения того, как выполнить каждый запрос из информации, уже известной о каждом объекте, используя систему, основанную на правилах. Например, существует много правил о том, как вычислять грани политопа. Грани могут быть вычислены из описания вершин политопа и из (возможно, избыточного) описания неравенства. polymake строит граф зависимостей, описывающий шаги для обработки каждого запроса, и выбирает наилучший путь с помощью алгоритма типа Дейкстры. [6]

polymake делит свою коллекцию функций и объектов на 10 различных групп, называемых приложениями. Они ведут себя как пространства имен C++. Приложение polytope было разработано первым и является самым большим. [7]

  • Распространенные: «вспомогательные» функции, используемые в других приложениях. [8]
  • Граф: манипулирование ориентированными и неориентированными графами. [11]
  • Группа: фокус на конечных группах перестановок. Основные свойства группы могут быть вычислены как характеры и классы сопряженности. [12]
  • Матроид: вычисление стандартных свойств матроида , таких как базы и схемы. Это приложение также может вычислять более сложные свойства, такие как полином Тутте матроида и реализация матроида с помощью многогранника. [14]
  • Политоп: более 230 функций или вычислений, которые можно выполнить с политопом. Эти функции варьируются по сложности от простого вычисления базовой информации о политопе (например, количество вершин, количество граней, тесты для симплициальных политопов и преобразование описания вершин в описание неравенства) до комбинаторных или алгебраических свойств (например, H-вектор , полином Эрхарта , базис Гильберта и диаграммы Шлегеля ). [7] Также есть много вариантов визуализации.
  • Тропические: функции для исследования тропической геометрии ; в частности, тропические гиперповерхности и тропические конусы. [16]

История развития

polymake версии 1.0 впервые появился в трудах DMV-семинара «Многогранники и оптимизация», состоявшегося в Обервольфахе в ноябре 1997 года. [2] Версия 1.0 содержала только приложение многогранников, но система «приложений» еще не была разработана. Версия 2.0 была выпущена в июле 2003 года, [17] а версия 3.0 была выпущена в 2016 году. [18] Последняя большая ревизия, версия 4.0, была выпущена в январе 2020 года. [19]

Взаимодействие с другими программными пакетами

polymake имеет высокомодульную конструкцию и, следовательно, демонстрирует отличное взаимодействие со сторонними программными пакетами для специализированных вычислений, тем самым предоставляя общий интерфейс и мост между различными инструментами. Пользователь может легко (и неосознанно) переключаться между использованием различных программных пакетов в процессе вычисления свойств политопа. [20]

Используется в polymake

Ниже приведен список сторонних программных пакетов, с которыми polymake может взаимодействовать, начиная с версии 4.0. Пользователи также могут писать новые файлы правил для взаимодействия с любым программным пакетом. Обратите внимание, что в этом списке есть некоторая избыточность (например, несколько различных пакетов могут использоваться для поиска выпуклой оболочки многогранника). Поскольку polymake использует файлы правил и граф зависимостей для вычисления свойств, [5] большинство этих программных пакетов являются необязательными. Однако некоторые из них становятся необходимыми для специализированных вычислений.

  • 4ti2: программный пакет для решения алгебраических, геометрических и комбинаторных задач на линейных пространствах
  • a-tint: теория тропического пересечения
  • azove: перечисление 0/1 вершин
  • барвинок: подсчет целых точек в параметризованных и непараметризованных многогранниках
  • cdd: метод двойного описания для преобразования между неравенством и вершинным описанием многогранника
  • Geomview : интерактивная программа 3D-просмотра
  • Gfan: веера Грёбнера и тропические сорта
  • GraphViz : программное обеспечение для визуализации графиков
  • гомология: вычисление групп гомологии симплициальных комплексов
  • LattE (перечисление точек решетки): подсчет точек решетки внутри многогранников и интегрирование по многогранникам
  • libnormaliz: аффинные моноиды , векторные конфигурации, решетчатые многогранники и рациональные конусы
  • lrs: реализация алгоритма обратного поиска для задачи перечисления вершин и задач выпуклой оболочки
  • mptopcom: вычисление триангуляции точечных конфигураций и матроидов с использованием параллельного обратного поиска
  • nauty: группы автоморфизмов графов
  • плантри: плоские триангуляции
  • permlib: установка стабилизатора и вычисления на орбите
  • PORTA: перечислить точки решетки многогранника
  • ppl: Библиотека многогранников Пармы
  • qhull: алгоритм Quickhull для выпуклых оболочек
  • single: система компьютерной алгебры для полиномиальных вычислений, с особым акцентом на коммутативную и некоммутативную алгебру, алгебраическую геометрию и теорию особенностей
  • эскиз: для создания линейных рисунков двух- или трехмерных твердых объектов
  • SplitsTree4 : филогенетические сети
  • sympol: инструмент для работы с симметричными многогранниками
  • threejs : библиотека JavaScript для анимированной 3D компьютерной графики
  • tikz : Пакеты TeX для программного создания графики
  • TropLi: для вычисления тропических линейных пространств матроидов
  • tosimplex: Двойной симплексный алгоритм, реализованный Томасом Опфером
  • Винчи: объемы многогранников

Используется совместно с polymake

  • jupyter-polymake: позволяет использовать polymake в блокнотах Jupyter .
  • OSCAR: Система исследований компьютерной алгебры с открытым исходным кодом в настоящее время находится в стадии разработки
  • PolymakeInterface: пакет для использования polymake в GAP .
  • PolyViewer: просмотрщик с графическим интерфейсом для файлов Polymake.

Ссылки

  1. ^ Официальный сайт
  2. ^ ab Gawrilow, Ewgenij; Joswig, Michael (2000-01-01). Kalai, Gil; Ziegler, Günter M. (ред.). polymake: a Framework for Analyzing Convex Polytopes . Polytopes—combinatorics and computing, DMV Seminar. Birkhäuser Basel. стр.  43–73 . doi :10.1007/978-3-0348-8438-9_2. ISBN 9783764363512.
  3. ^ Ассарф, Бенджамин; Гаврилов, Евгений; Герр, Катрин; Йосвиг, Майкл; Лоренц, Бенджамин; Паффенхольц, Андреас; Рен, Томас (01 марта 2017 г.). «Вычисление выпуклых оболочек и подсчет целых точек с помощью Polymake». Математическое программирование вычислений . 9 (1): 1–38 . arXiv : 1408.4653 . doi : 10.1007/s12532-016-0104-z. ISSN  1867-2957. S2CID  5594262.
  4. ^ "Polymake - Математическое программное обеспечение - swMATH".
  5. ^ аб Йосвиг, Майкл; Мюллер, Бенджамин; Паффенхольц, Андреас (17 февраля 2009 г.). «Полимак и решетчатые многогранники». arXiv : 0902.2919 [math.CO].
  6. ^ ab Gawrilow, Ewgenij; Joswig, Michael (2005-07-13). "Геометрическое рассуждение с помощью polymake". arXiv : math/0507273 .
  7. ^ ab "документация polymake, приложение: polytope". polymake.org . Получено 2016-06-11 .
  8. ^ "документация polymake, приложение: общее". polymake.org . Получено 2016-06-11 .
  9. ^ "документация polymake, приложение: вентилятор". polymake.org . Получено 2016-06-11 .
  10. ^ "документация polymake, приложение: fulton". polymake.org . Получено 2016-06-11 .
  11. ^ "документация polymake, приложение: график". polymake.org . Получено 2016-06-11 .
  12. ^ "документация polymake, приложение: группа". polymake.org . Получено 2016-06-11 .
  13. ^ "документация polymake, приложение: идеально". polymake.org . Получено 2016-06-11 .
  14. ^ "документация polymake, приложение: matroid". polymake.org . Получено 2016-06-11 .
  15. ^ "документация polymake, приложение: топаз". polymake.org . Получено 2016-06-11 .
  16. ^ "документация polymake, приложение: тропический". polymake.org . Получено 2016-06-11 .
  17. ^ "выпуск polymake 2.0". www.computational-geometry.org . Получено 2023-11-13 .
  18. ^ "Polymake 3.0". GitHub . Получено 28.06.2016 .
  19. ^ "Polymake 4.0 [polymake wiki]". polymake.org . Получено 2023-11-13 .
  20. ^ Gawrilow, Ewgenij; Joswig, Michael (2001-06-01). "Polymake: подход к модульному проектированию программного обеспечения в вычислительной геометрии". Труды семнадцатого ежегодного симпозиума по вычислительной геометрии . SCG '01. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр.  222– 231. doi :10.1145/378583.378673. ISBN 978-1-58113-357-8. S2CID  16519425.
Взято с "https://en.wikipedia.org/w/index.php?title=Polymake&oldid=1241365087"