Полимейк
 | |
 | |
| Оригинальный автор(ы) | Евгений Гаврилов и Михаэль Йосвиг |
|---|---|
| Первоначальный выпуск | 1997 год |
| Стабильная версия | 4.11 / 6 ноября 2023 г |
| Репозиторий | |
| Написано в | С++ , Перл |
| Операционная система | Линукс , Мак |
| Доступно в | Английский |
| Лицензия | Стандартная общественная лицензия GNU |
| Веб-сайт | полимейк |
Polymake — программное обеспечение для алгоритмической обработки выпуклых многогранников . [1]
Хотя это в первую очередь инструмент для изучения комбинаторики и геометрии выпуклых многогранников и многогранников , [2] теперь он также способен работать с симплициальными комплексами , матроидами , веерами многогранников, графами , тропическими объектами, торическими многообразиями и другими объектами. В частности, его способность вычислять выпуклую оболочку и точки решетки многогранника оказалась вполне полезной для различных видов исследований. [3]
Polymake цитировался в более чем 300 недавних статьях, проиндексированных Zentralblatt MATH , о чем свидетельствует его запись в базе данных swMATH. [4]
Специальные функции и приложения
[ редактировать ]Polymake имеет несколько особенностей, делающих его особенным в работе.
Во-первых, Polymake можно использовать в сценарии Perl . Более того, пользователи могут расширять Polymake и определять новые объекты, свойства, правила вычисления свойств и алгоритмы. [5]
Во-вторых, он демонстрирует внутреннюю схему клиент-сервер, позволяющую использовать Perl для управления объектами и интерфейсами, а также C++ для математических алгоритмов. [6] Сервер хранит информацию о каждом объекте (например, многограннике), а клиент отправляет запросы на вычисление свойств. Сервер должен определить, как выполнить каждый запрос на основе уже известной информации о каждом объекте, используя систему, основанную на правилах. Например, существует множество правил вычисления граней многогранника. Фасеты можно вычислить на основе описания вершин многогранника и на основе (возможно, избыточного) описания неравенства. Polymake строит граф зависимостей, описывающий этапы обработки каждого запроса, и выбирает лучший путь с помощью алгоритма типа Дейкстры. [6]
Polymake делит свою коллекцию функций и объектов на 10 различных групп, называемых приложениями. Они ведут себя как пространства имен C++. Приложение «Многогранник» было разработано первым и является самым крупным. [7]
- Общие: «вспомогательные» функции, используемые в других приложениях. [8]
- Веер: функции для многогранных комплексов (которые обобщают симплициальные комплексы ), плоские рисунки 3-многогранников, многогранные вееры и подразделения точек или векторов. [9]
- Фултон: вычисления с нормальными торическими многообразиями . Он назван в честь Уильяма Фултона , автора книги «Введение в торические разновидности». [10]
- Граф: манипулирование ориентированными и неориентированными графами. [11]
- Группа: сосредоточьтесь на конечных группах перестановок. Основные свойства группы можно рассчитать как символы и классы сопряженности. [12]
- Идеал: вычисления над полиномиальными идеалами: базис Грёбнера , полином Гильберта и радикалы . [13]
- Матроид: вычисление стандартных свойств матроида , таких как основания и схемы. Это приложение также может вычислять более сложные свойства, такие как полином Тутте матроида и реализацию матроида с помощью многогранника. [14]
- Многогранник: более 230 функций или вычислений, которые можно выполнить с помощью многогранника. Эти функции варьируются по сложности от простого вычисления базовой информации о многограннике (например, количества вершин, количества фасетов, проверки симплициальных многогранников и преобразования описания вершины в описание неравенства) до комбинаторных или алгебраических свойств (например, H-вектор , полином Эрхарта , базис Гильберта и диаграммы Шлегеля ). [7] Также существует множество вариантов визуализации.
- Топаз: функции, относящиеся к абстрактным симплициальным комплексам . [15] Многие сложные топологические вычисления над симплициальными комплексами могут быть выполнены, например, для групп гомологии , ориентации и фундаментальной группы . Существует также комбинаторный набор свойств, которые можно вычислить, например, диаграммы Шеллинга и Хассе .
- Tropical: функции для изучения тропической геометрии ; в частности, тропические гиперповерхности и тропические конусы. [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 вершин
- barvinok : подсчет целых точек в параметризованных и непараметризованных многогранниках
- cdd : метод двойного описания для преобразования между неравенством и описанием вершин многогранника.
- Geomview : программа интерактивного 3D-просмотра.
- Gfan : поклонники Грёбнера и тропические сорта.
- GraphViz : программа для визуализации графиков.
- гомологии : вычисление групп гомологии симплициальных комплексов
- LattE (перечисление точек решетки): подсчет точек решетки внутри многогранников и интегрирование по многогранникам.
- libnormaliz : аффинные моноиды , векторные конфигурации, решетчатые многогранники и рациональные конусы.
- lrs : реализация алгоритма обратного поиска для задачи перечисления вершин и выпуклой оболочки . задач
- mptopcom : вычисление триангуляций точечных конфигураций и матроидов с использованием параллельного обратного поиска.
- nauty : группы автоморфизмов графов
- plantri : плоские триангуляции
- permlib : установить стабилизатор и вычисления на орбите
- PORTA : перечислить точки решетки многогранника.
- ppl : Библиотека Пармских многогранников
- qhull : Алгоритм Quickhull для выпуклых оболочек
- сингулярный : система компьютерной алгебры для полиномиальных вычислений с особым упором на коммутативную и некоммутативную алгебру, алгебраическую геометрию и теорию особенностей.
- эскиз : для создания линейных рисунков двух- или трехмерных твердых объектов.
- SplitsTree4 : филогенетические сети
- sympol : инструмент для работы с симметричными многогранниками
- Threejs : библиотека JavaScript для анимированной 3D-компьютерной графики.
- tikz : пакеты TeX для программного создания графики.
- TropLi : для вычисления тропических линейных пространств матроидов.
- tosiplex: алгоритм двойного симплекса, реализованный Томасом Опфером.
- Винчи : объемы многогранников
Используется совместно с Polymake.
[ редактировать ]- jupyter-polymake : позволяет использовать Polymake в блокнотах Jupyter .
- OSCAR : система исследования компьютерной алгебры с открытым исходным кодом, которая в настоящее время находится в стадии разработки.
- PolymakeInterface : пакет для использования Polymake в GAP .
- PolyViewer : с графическим интерфейсом . программа просмотра файлов Polymake
Ссылки
[ редактировать ]- ^ Официальный сайт
- ^ Jump up to: а б Гаврилов, Евгений; Йосвиг, Майкл (1 января 2000 г.). Калаи, Гил; Циглер, Гюнтер М. (ред.). Polymake: платформа для анализа выпуклых многогранников . Многогранники — комбинаторика и вычисления, Семинар DMV. Биркхойзер Базель. стр. 43–73. дои : 10.1007/978-3-0348-8438-9_2 . ISBN 9783764363512 .
- ^ Ассарф, Бенджамин; Гаврилов, Евгений; Герр, Катрин; Йосвиг, Майкл; Лоренц, Бенджамин; Паффенхольц, Андреас; Рен, Томас (01 марта 2017 г.). «Вычисление выпуклых оболочек и подсчет целых точек с помощью Polymake» . Математическое программирование вычислений . 9 (1): 1–38. arXiv : 1408.4653 . дои : 10.1007/s12532-016-0104-z . ISSN 1867-2957 . S2CID 5594262 .
- ^ «Polymake — Математическое программное обеспечение — swMATH» .
- ^ Jump up to: а б Йосвиг, Майкл; Мюллер, Бенджамин; Паффенхольц, Андреас (17 февраля 2009 г.). «Полимак и решетчатые многогранники». arXiv : 0902.2919 [ math.CO ].
- ^ Jump up to: а б Гаврилов, Евгений; Йосвиг, Майкл (13 июля 2005 г.). «Геометрические рассуждения с полимейком». arXiv : math/0507273 .
- ^ Jump up to: а б «документация Polymake, приложение: многогранник» . сайт Polymake.org . Проверено 11 июня 2016 г.
- ^ «документация Polymake, приложение: общее» . сайт Polymake.org . Проверено 11 июня 2016 г.
- ^ «документация Polymake, приложение: вентилятор» . сайт Polymake.org . Проверено 11 июня 2016 г.
- ^ «Документация Polymake, приложение: Фултон» . сайт Polymake.org . Проверено 11 июня 2016 г.
- ^ «документация Polymake, приложение: график» . сайт Polymake.org . Проверено 11 июня 2016 г.
- ^ «документация Polymake, приложение: группа» . сайт Polymake.org . Проверено 11 июня 2016 г.
- ^ «Документация Polymake, приложение: идеально» . сайт Polymake.org . Проверено 11 июня 2016 г.
- ^ «документация Polymake, приложение: maroid» . сайт Polymake.org . Проверено 11 июня 2016 г.
- ^ «документация Polymake, приложение: топаз» . сайт Polymake.org . Проверено 11 июня 2016 г.
- ^ «документация Polymake, применение: тропическое» . сайт Polymake.org . Проверено 11 июня 2016 г.
- ^ «Выпуск Polymake 2.0» . www.computational-geometry.org . Проверено 13 ноября 2023 г.
- ^ «Полимейк 3.0» . Гитхаб . Проверено 28 июня 2016 г.
- ^ «Polymake 4.0 [polymake wiki]» . сайт Polymake.org . Проверено 13 ноября 2023 г.
- ^ Гаврилов, Евгений; Йосвиг, Майкл (1 июня 2001 г.). «Polymake: подход к модульному проектированию программного обеспечения в вычислительной геометрии» . Материалы семнадцатого ежегодного симпозиума по вычислительной геометрии . СКГ '01. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 222–231. дои : 10.1145/378583.378673 . ISBN 978-1-58113-357-8 . S2CID 16519425 .