Алгоритмическая топология или вычислительная топология - это подполе топологии, пересекающееся с областями информатики , в частности, с вычислительной геометрией и теорией сложности вычислений .
Основная задача алгоритмической топологии, как следует из названия, заключается в разработке эффективных алгоритмов для решения проблем, которые естественным образом возникают в таких областях, как вычислительная геометрия , графика , робототехника , структурная биология и химия , с использованием методов вычислимой топологии . [1] [2]
Основные алгоритмы по предметной области
Алгоритмическая теория 3-многообразий
Большое семейство алгоритмов, касающихся трехмерных многообразий, вращается вокруг теории нормальной поверхности , которая представляет собой выражение, охватывающее несколько методов превращения проблем теории трехмерных многообразий в задачи целочисленного линейного программирования.
- Алгоритм распознавания 3-х сфер Рубинштейна и Томпсона . Это алгоритм , который принимает в качестве входной триангулированного 3-многообразия и определяет , является ли многообразие гомеоморфно к 3-мерной сфере . Он имеет экспоненциальное время выполнения по количеству тетраэдрических симплексов в исходном 3-многообразии, а также экспоненциальный профиль памяти. Более того, это реализовано в программном комплексе Regina . [3] Саул Шлеймер показал, что проблема заключается в классе сложности NP . [4] Кроме того, Рафаэль Центнер показал, что проблема заключается в классе сложности coNP, [5] при условии, что обобщенная гипотеза Римана верна. Он использует инстантонную калибровочную теорию, теорему геометризации трехмерных многообразий и последующую работу Грега Куперберга [6] о сложности обнаружения узлов.
- Подключения суммы разложение 3-многообразий также реализуется в Regina , имеет экспоненциальное время выполнения и на основе аналогичного алгоритма с алгоритмом распознавания 3-сферы.
- Определение того, что трехмерное многообразие Зейферта-Вебера не содержит несжимаемой поверхности, было реализовано алгоритмически Бертоном, Рубинштейном и Тиллманом [7] и основано на теории нормальных поверхностей.
- Алгоритм Мэннинг является алгоритм поиска гиперболических структур на 3-многообразиях, фундаментальная группа имеет решение проблемы слова . [8]
В настоящее время разложение JSJ не реализовано алгоритмически в компьютерном программном обеспечении. Нет и разложения тела сжатия. Есть несколько очень популярных и успешных эвристик, таких как SnapPea, который успешно вычисляет приближенные гиперболические структуры на триангулированных 3-многообразиях. Известно, что полную классификацию трехмерных многообразий можно провести алгоритмически. [9]
Алгоритмы преобразования
- SnapPea реализует алгоритм преобразования плоской диаграммы узлов или звеньев в триангуляцию с выступом. Этот алгоритм имеет примерно линейное время выполнения по количеству пересечений на диаграмме и низкий профиль памяти. Алгоритм аналогичен алгоритму Виртингера для построения представлений фундаментальной группы дополнительных звеньев, заданных плоскими диаграммами. Точно так же SnapPea может преобразовывать хирургические представления трехмерных многообразий в триангуляции представленных трехмерных многообразий.
- Д. Терстон и Ф. Костантино разработали процедуру построения триангулированного 4-многообразия из триангулированного 3-многообразия. Точно так же его можно использовать для построения хирургических представлений триангулированных трехмерных многообразий, хотя процедура явно не написана как алгоритм, в принципе, она должна иметь полиномиальное время выполнения по количеству тетраэдров данной триангуляции трехмерного многообразия. [10]
- У С. Шлеймера есть алгоритм, который создает триангулированное 3-многообразие при заданном вводе слова (в генераторах скручивания Дена ) для группы классов отображений поверхности. Трехмерное многообразие - это то, которое использует это слово в качестве присоединяющего отображения для расщепления Хегора трехмерного многообразия. Алгоритм основан на концепции многоуровневой триангуляции .
Алгоритмическая теория узлов
- Как известно, задача определения рода узла имеет класс сложности PSPACE .
- Существуют алгоритмы с полиномиальным временем вычисления полинома Александера узла. [12]
Вычислительная гомотопия
- Вычислительные методы для гомотопических групп сфер .
- Вычислительные методы решения систем полиномиальных уравнений .
- Браун алгоритм вычисления гомотопических групп пространств , которые являются конечными Постников комплексы , [13] , хотя это не так широко считается осуществимым.
Вычислительная гомология
Вычисление групп гомологии в клеточных комплексах сводится к приведению граничных матриц в нормальную форму Смита . Хотя это полностью решаемая проблема алгоритмически, существуют различные технические препятствия для эффективных вычислений для больших комплексов. Есть два центральных препятствия. Во-первых, базовый алгоритм формы Смита имеет кубическую сложность по размеру задействованной матрицы, поскольку он использует операции со строками и столбцами, что делает его непригодным для больших комплексов ячеек. Во-вторых, промежуточные матрицы, полученные в результате применения алгоритма формы Смита, заполняются, даже если одна из них начинается и заканчивается разреженными матрицами.
- Эффективные и вероятностные алгоритмы нормальной формы Смита, найденные в библиотеке LinBox .
- Простые гомотопические редукции для предварительных вычислений гомологии, как в программном пакете Perseus .
- Алгоритмы для вычисления упорных гомологий с отфильтрованными комплексами, как и в TDAstats пакета R. [14]
Смотрите также
- Вычислимая топология (исследование топологической природы вычислений)
- Вычислительная геометрия
- Цифровая топология
- Топологический анализ данных
- Пространственно-временные рассуждения
- Экспериментальная математика
- Геометрическое моделирование
Рекомендации
- ^ Афра J. Zomorodian, топологии для вычислений , Cambridge, 2005, XI
- ^ Блевинс, Энн Сайзмор; Bassett, Danielle S. (2020), Sriraman, Bharath (ed.), «Топология в биологии», Справочник по математике искусств и наук , Cham: Springer International Publishing, стр. 1-23, DOI : 10.1007 / 978 -3-319-70658-0_87-1 , ISBN 978-3-319-70658-0
- ^ Б. ~ Бертон. Представляем Regina, программу для топологии 3-многообразий, Experimental Mathematics 13 (2004), 267–272.
- ^ Шлеймер, Саул (2011). «Признание сферы лежит в NP» (PDF) - через Университет Уорика .
- ^ Центнер, Рафаэль (2018). «Целочисленные гомологии 3-сферы допускают неприводимые представления в SL (2, C)». Математический журнал герцога . 167 (9): 1643–1712. arXiv : 1605.08530 . DOI : 10.1215 / 00127094-2018-0004 . S2CID 119275434 .
- ^ Куперберг, Грег (2014). «Узловатость есть в NP по модулю GRH». Успехи в математике . 256 : 493–506. arXiv : 1112.0845 . DOI : 10.1016 / j.aim.2014.01.007 . S2CID 12634367 .
- ^ Бертон, Бенджамин А .; Hyam Rubinstein, J .; Тилльманн, Стефан (2009). «Додекаэдрическое пространство Вебера-Зейферта не является Хакеном». Труды Американского математического общества . 364 (2). arXiv : 0909.4625 . DOI : 10.1090 / S0002-9947-2011-05419-X .
- ^ Дж. Маннинг, Алгоритмическое обнаружение и описание гиперболических структур на 3-многообразиях с разрешимой проблемой слов, Геометрия и топология 6 (2002) 1–26
- ^ С. Матвеев, Алгоритмическая топология и классификация трехмерных многообразий, Springer-Verlag 2003
- ^ Костантино, Франческо; Терстон, Дилан (2008). «Трехмерные многообразия эффективно связывают четырехмерные многообразия». Журнал топологии . 1 (3): 703–745. arXiv : математика / 0506577 . DOI : 10,1112 / jtopol / jtn017 . S2CID 15119190 .
- ^ Хасс, Джоэл ; Лагариас, Джеффри К .; Пиппенгер, Николас (1999), "Вычислительная сложность проблем узлов и связей", Журнал ACM , 46 (2): 185–211, arXiv : math / 9807016 , doi : 10.1145 / 301970.301971 , S2CID 125854.
- ^ " Main_Page ", Атлас узлов .
- ^ Браун, Эдгар Х. (1957), "Конечная Вычислимость Постники Комплексов", Анналы математики (2) , 65 : 1-20, DOI : 10,2307 / 1969664 CS1 maint: обескураженный параметр ( ссылка )
- ^ Вадхва, Рауль; Уильямсон, Дрю; Дхаван, Эндрю; Скотт, Джейкоб (2018). «TDAstats: R конвейер для вычисления устойчивой гомологии в топологическом анализе данных» . Журнал открытого программного обеспечения . 3 (28): 860. Полномочный код : 2018JOSS .... 3..860R . DOI : 10,21105 / joss.00860 .
Внешние ссылки
- Архив программного обеспечения CompuTop
- Практикум по применению топологии в науке и технике
- Вычислительная топология в Стэнфордском университете
- Программное обеспечение для вычислительной гомологии (CHomP) в Университете Рутгерса .
- Программное обеспечение вычислительной гомологии (RedHom) в Ягеллонском университете .
- Программный проект Perseus для (постоянной) гомологии .
- Программное обеспечение javaPlex Persistent Homology в Стэнфорде .
- PHAT: набор инструментов для алгоритмов постоянной гомологии .
Книги
- Томаш Качиньски; Константин Мишайков; Мариан Мрозек (2004). Вычислительные гомологии . Springer. ISBN 0-387-40853-3.
- Афра Дж. Зомородян (2005). Топология для вычислений . Кембридж. ISBN 0-521-83666-2.
- Вычислительная топология: введение , Герберт Эдельсбруннер, Джон Л. Харер, книжный магазин AMS, 2010 г., ISBN 978-0-8218-4925-5