Вычислительная топология

Алгоритмическая топология , или вычислительная топология , является подразделом топологии , пересекающимся с областями компьютерной науки , в частности, с вычислительной геометрией и теорией сложности вычислений .

Основной задачей алгоритмической топологии, как следует из ее названия, является разработка эффективных алгоритмов для решения задач, которые естественным образом возникают в таких областях, как вычислительная геометрия , графика , робототехника , социальные науки , структурная биология и химия , с использованием методов вычислимой топологии . ^{[1] [2] [3]}

Основные алгоритмы по предметной области

Алгоритмическая теория 3-многообразий

Большое семейство алгоритмов, касающихся 3-многообразий , вращается вокруг теории нормальных поверхностей , которая представляет собой фразу, охватывающую несколько методов превращения задач теории 3-многообразий в задачи целочисленного линейного программирования.

• Алгоритм распознавания 3-сфер Рубинштейна и Томпсона . Это алгоритм, который принимает в качестве входных данных триангулированное 3-многообразие и определяет, гомеоморфно ли многообразие 3-сфере . Он имеет экспоненциальное время выполнения по числу тетраэдральных симплексов в исходном 3-многообразии, а также экспоненциальный профиль памяти. Более того, он реализован в программном пакете Regina . ^[4] Сол Шлеймер продолжил, показав, что проблема лежит в классе сложности NP . ^[5] Кроме того, Рафаэль Центнер показал, что проблема лежит в классе сложности coNP, ^[6] при условии, что верна обобщенная гипотеза Римана. Он использует теорию инстантонной калибровки, теорему геометризации 3-многообразий и последующую работу Грега Куперберга ^[7] по сложности обнаружения заузленности.
• Разложение 3-многообразий методом коннективной суммы также реализовано в Regina , имеет экспоненциальное время выполнения и основано на алгоритме, аналогичном алгоритму распознавания 3-сфер.
• Определение того, что 3-многообразие Зейферта-Вебера не содержит несжимаемой поверхности, было алгоритмически реализовано Бертоном, Рубинштейном и Тиллманном ^[8] и основано на теории нормальных поверхностей.
• Алгоритм Мэннинга — это алгоритм для поиска гиперболических структур на 3-многообразиях, фундаментальная группа которых имеет решение проблемы тождества . ^[9]

В настоящее время разложение JSJ не реализовано алгоритмически в компьютерном программном обеспечении. Также не реализовано разложение компрессионного тела. Существуют некоторые очень популярные и успешные эвристики, такие как SnapPea , которая имеет большой успех в вычислении приближенных гиперболических структур на триангулированных 3-многообразиях. Известно, что полная классификация 3-многообразий может быть выполнена алгоритмически, ^[10] на самом деле, известно, что решение вопроса об эквивалентности (гомеоморфности) двух замкнутых ориентированных 3-многообразий, заданных триангуляциями (симплициальными комплексами), является элементарно рекурсивным . ^[11] Это обобщает результат о распознавании 3-сфер.

Алгоритмы преобразования

• SnapPea реализует алгоритм для преобразования плоской диаграммы узла или связи в остроконечную триангуляцию. Этот алгоритм имеет примерно линейное время выполнения в зависимости от количества пересечений в диаграмме и низкий профиль памяти. Алгоритм похож на алгоритм Виртингера для построения презентаций фундаментальной группы дополнений связей, заданных плоскими диаграммами. Аналогично, SnapPea может преобразовывать хирургические презентации 3-многообразий в триангуляции представленного 3-многообразия.
• У Д. Терстона и Ф. Костантино есть процедура для построения триангулированного 4-многообразия из триангулированного 3-многообразия. Аналогично, ее можно использовать для построения хирургических представлений триангулированных 3-многообразий, хотя процедура явно не записана как алгоритм, в принципе она должна иметь полиномиальное время выполнения по числу тетраэдров заданной триангуляции 3-многообразия. ^[12]
• У Шлеймера есть алгоритм, который создает триангулированное 3-многообразие, если на вход подать слово (в генераторах твиста Дена ) для группы классов отображения поверхности. 3-многообразие — это то, которое использует слово в качестве прикрепляющей карты для разбиения Хегора 3-многообразия. Алгоритм основан на концепции слоистой триангуляции .

Теория алгоритмических узлов

• Известно, что определение того, является ли узел тривиальным, относится к классам сложности NP ^[13], а также co-NP ^[14] .
• Известно, что задача определения рода узла имеет класс сложности PSPACE . ^[13]
• Существуют полиномиальные алгоритмы для вычисления полинома Александера узла. ^[15]
• Полином Джонса , полином HOMFLY и инварианты Решетихина–Тураева являются фиксированными параметрами tracktable , в то время как полином Джонса, как известно, является #P-hard . ^[16] Вычисление первого коэффициента полинома HOMFLYPT и Кауфмана выполняется в P. ^[17]
• Аддитивное приближение полинома Джонса является BQP-полным , т.е. эквивалентно сложным, как и квантовые алгоритмы с полиномиальным временем. ^[18]
• Если даны два (ручных) узла с помощью диаграмм связей, то решение об их эквивалентности является ER . Это устанавливается путем сведения эквивалентности узлов ( изотопии ) к эквивалентности ( гомеоморфии ) ассоциированных дополнений узлов , которые являются 3-многообразиями , которые, в свою очередь, могут быть закодированы триангуляциями . Поскольку эти дополнения узлов являются многообразиями Хакена , то затем используется результат о том, что проблема эквивалентности этих многообразий находится в ER. Кажется, для этого нет хорошей ссылки, эти результаты разбросаны по литературе в этой области, но хорошо известны сообществу.

Вычислительная гомотопия

• Методы вычисления гомотопических групп сфер .
• Вычислительные методы решения систем полиномиальных уравнений .
• У Брауна есть алгоритм для вычисления гомотопических групп пространств, являющихся конечными комплексами Постникова ^[19] , хотя он не считается широко реализуемым.

Вычислительная гомология

Вычисление групп гомологии клеточных комплексов сводится к приведению граничных матриц к нормальной форме Смита . Хотя это полностью решенная задача алгоритмически, существуют различные технические препятствия для эффективного вычисления для больших комплексов. Есть два центральных препятствия. Во-первых, базовый алгоритм формы Смита имеет кубическую сложность по размеру задействованной матрицы, поскольку он использует операции над строками и столбцами, что делает его непригодным для больших клеточных комплексов. Во-вторых, промежуточные матрицы, которые получаются в результате применения алгоритма формы Смита, заполняются, даже если начинать и заканчивать разреженными матрицами.

• Эффективные и вероятностные алгоритмы нормальной формы Смита, представленные в библиотеке LinBox.
• Простые гомотопические редукции для предварительной обработки гомологических вычислений, как в программном пакете Perseus.
• Алгоритмы для вычисления постоянной гомологии отфильтрованных комплексов, как в пакете TDAstats R. [ ^20]

Смотрите также

• Вычислительная топология (изучение топологической природы вычислений)
• Вычислительная геометрия
• Цифровая топология
• Топологический анализ данных
• Пространственно-временное мышление
• Экспериментальная математика
• Геометрическое моделирование

Ссылки

1. Афра Дж. Зомородян, Топология для вычислений, Кембридж, 2005, xi
2. Блевинс, Энн Сайзмор; Бассетт, Даниэль С. (2020), Шрираман, Бхарат (ред.), «Топология в биологии», Справочник по математике искусств и наук , Cham: Springer International Publishing, стр. 1–23, doi : 10.1007/978-3-319-70658-0_87-1, ISBN 978-3-319-70658-0, S2CID  226695484
3. Чиу, Линди (26 марта 2024 г.). «Топологи решают проблему размещения опросов». Журнал Quanta . Получено 1 апреля 2024 г.
4. Бертон, Бенджамин А. (2004). «Введение в Regina, программное обеспечение для топологии 3-многообразий» (PDF) . Экспериментальная математика . 13 (3): 267–272. doi :10.1080/10586458.2004.10504538. S2CID  16566807.
5. Шлеймер, Саул (2011). «Распознавание сфер лежит в NP» (PDF) – через Университет Уорика .
6. Zentner, Raphael (2018). «Целочисленные гомологии 3-сфер допускают неприводимые представления в SL(2,C)». Duke Mathematical Journal . 167 (9): 1643–1712. arXiv : 1605.08530 . doi :10.1215/00127094-2018-0004. S2CID  119275434.
7. Куперберг, Грег (2014). «Узловатость есть в NP, по модулю GRH». Успехи в математике . 256 : 493–506. arXiv : 1112.0845 . doi : 10.1016/j.aim.2014.01.007 . S2CID  12634367.
8. Бертон, Бенджамин А.; Хайам Рубинштейн, Дж.; Тиллманн, Стефан (2009). «Додекаэдрическое пространство Вебера-Зейферта не является пространством Хакена». Труды Американского математического общества . 364 (2): 911–932. arXiv : 0909.4625 . doi : 10.1090/S0002-9947-2011-05419-X. S2CID  18435885.
9. Дж. Мэннинг, Алгоритмическое обнаружение и описание гиперболических структур на 3-многообразиях с разрешимой проблемой поиска слов, Геометрия и топология 6 (2002) 1–26
10. С.Матвеев, Алгоритмическая топология и классификация 3-многообразий, Springer-Verlag 2003
11. Куперберг, Грег (2019). «Алгоритмический гомеоморфизм 3-многообразий как следствие геометризации». Pacific Journal of Mathematics . 301 : 189–241. arXiv : 1508.06720 . doi : 10.2140/pjm.2019.301.189. S2CID  119298413.
12. Костантино, Франческо; Терстон, Дилан (2008). «3-многообразия эффективно связывают 4-многообразия». Журнал топологии . 1 (3): 703–745. arXiv : math/0506577 . doi :10.1112/jtopol/jtn017. S2CID  15119190.
13. Хасс, Джоэл ; Лагариас, Джеффри К.; Пиппенджер , Николас (1999), «Вычислительная сложность задач узлов и связей», Журнал ACM , 46 (2): 185–211, arXiv : math/9807016 , doi : 10.1145/301970.301971, S2CID  125854
14. Лакенби, Марк (2021), «Эффективная сертификация узловатости и нормы Терстона», Успехи в математике , 387 : 107796, arXiv : 1604.00290 , doi : 10.1016/j.aim.2021.107796, S2CID  119307517
15. "Main_Page", Атлас узлов .
16. Мария, Клеман (2019). «Параметризованная сложность квантовых инвариантов». arXiv : 1910.00477 [math.GT].
17. Przytycki, Jozef H. (2017). «Первый коэффициент полиномов Хомфлипта и Кауфмана: доказательство Вертигана полиномиальной сложности с использованием динамического программирования». arXiv : 1707.07733 [math.GT].
18. Ааронов, Дорит; Джонс, Воган; Ландау, Зеф (2005). «Полиномиальный квантовый алгоритм для аппроксимации полинома Джонса». arXiv : quant-ph/0511096 .
19. Браун, Эдгар Х. (1957), «Конечная вычислимость комплексов Постникова», Annals of Mathematics (2) , 65 (1): 1–20, doi :10.2307/1969664, JSTOR  1969664
20. Вадхва, Рауль; Уильямсон, Дрю; Дхаван, Эндрю; Скотт, Джейкоб (2018). «TDAstats: конвейер R для вычисления постоянной гомологии в топологическом анализе данных». Журнал программного обеспечения с открытым исходным кодом . 3 (28): 860. Bibcode : 2018JOSS ....3..860R. doi : 10.21105/joss.00860 . PMC 7771879. PMID  33381678. 

Внешние ссылки

• Архив программного обеспечения CompuTop
• Семинар по применению топологии в науке и технике
• Вычислительная топология в Стэнфордском университете. Архивировано 22 июня 2007 г. на Wayback Machine.
• Программное обеспечение для вычислительной гомологии (CHomP) в Ратгерском университете.
• Программное обеспечение для вычислительной гомологии (RedHom) в Ягеллонском университете. Архивировано 15 июля 2013 г. на Wayback Machine .
• Программный проект Perseus для (постоянной) гомологии.
• Программное обеспечение javaPlex Persistent Homology в Стэнфорде.
• PHAT: набор инструментов для алгоритмов постоянной гомологии.

Книги

• Томаш Качиньский; Константин Мишайков; Мариан Мрозек (2004). Вычислительная гомология. Спрингер. ISBN 0-387-40853-3.
• Афра Дж. Зомородян (2005). Топология для вычислений. Кембридж. ISBN 0-521-83666-2.
• Вычислительная топология: введение , Герберт Эдельсбруннер, Джон Л. Харер, Книжный магазин AMS, 2010, ISBN 978-0-8218-4925-5