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

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

Основной задачей алгоритмической топологии, как следует из ее названия, является разработка эффективных алгоритмов для решения задач, которые естественным образом возникают в таких областях, как вычислительная геометрия , графика , робототехника , социальные науки , структурная биология и химия , с использованием методов вычислимой топологии . ^[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]

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

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

Ссылки

^ Афра Дж. Зомородян, Топология для вычислений, Кембридж, 2005, xi
^ Блевинс, Энн Сайзмор; Бассетт, Даниэль С. (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
^ Чиу, Линди (26 марта 2024 г.). «Топологи решают проблему размещения опросов». Журнал Quanta . Получено 1 апреля 2024 г.
^ Бертон, Бенджамин А. (2004). «Введение в Regina, программное обеспечение для топологии 3-многообразий» (PDF) . Экспериментальная математика . 13 (3): 267–272. doi :10.1080/10586458.2004.10504538. S2CID 16566807.
^ Шлеймер, Саул (2011). «Распознавание сфер лежит в NP» (PDF) – через Университет Уорика .
^ 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.
^ Куперберг, Грег (2014). «Узловатость есть в NP, по модулю GRH». Успехи в математике . 256 : 493–506. arXiv : 1112.0845 . doi : 10.1016/j.aim.2014.01.007 . S2CID 12634367.
^ Бертон, Бенджамин А.; Хайам Рубинштейн, Дж.; Тиллманн, Стефан (2009). «Додекаэдрическое пространство Вебера-Зейферта не является пространством Хакена». Труды Американского математического общества . 364 (2): 911–932. arXiv : 0909.4625 . doi : 10.1090/S0002-9947-2011-05419-X. S2CID 18435885.
^ Дж. Мэннинг, Алгоритмическое обнаружение и описание гиперболических структур на 3-многообразиях с разрешимой проблемой поиска слов, Геометрия и топология 6 (2002) 1–26
^ С.Матвеев, Алгоритмическая топология и классификация 3-многообразий, Springer-Verlag 2003
^ Куперберг, Грег (2019). «Алгоритмический гомеоморфизм 3-многообразий как следствие геометризации». Pacific Journal of Mathematics . 301 : 189–241. arXiv : 1508.06720 . doi : 10.2140/pjm.2019.301.189. S2CID 119298413.
^ Костантино, Франческо; Терстон, Дилан (2008). «3-многообразия эффективно связывают 4-многообразия». Журнал топологии . 1 (3): 703–745. arXiv : math/0506577 . doi :10.1112/jtopol/jtn017. S2CID 15119190.
^ ab Хасс, Джоэл ; Лагариас, Джеффри К.; Пиппенджер , Николас (1999), «Вычислительная сложность задач узлов и связей», Журнал ACM , 46 (2): 185–211, arXiv : math/9807016 , doi : 10.1145/301970.301971, S2CID 125854
^ Лакенби, Марк (2021), «Эффективная сертификация узловатости и нормы Терстона», Успехи в математике , 387 : 107796, arXiv : 1604.00290 , doi : 10.1016/j.aim.2021.107796, S2CID 119307517
^ "Main_Page", Атлас узлов .
^ Мария, Клеман (2019). «Параметризованная сложность квантовых инвариантов». arXiv : 1910.00477 [math.GT].
^ Przytycki, Jozef H. (2017). «Первый коэффициент полиномов Хомфлипта и Кауфмана: доказательство Вертигана полиномиальной сложности с использованием динамического программирования». arXiv : 1707.07733 [math.GT].
^ Ааронов, Дорит; Джонс, Воган; Ландау, Зеф (2005). «Полиномиальный квантовый алгоритм для аппроксимации полинома Джонса». arXiv : quant-ph/0511096 .
^ Браун, Эдгар Х. (1957), «Конечная вычислимость комплексов Постникова», Annals of Mathematics (2) , 65 (1): 1–20, doi :10.2307/1969664, JSTOR 1969664
^ Вадхва, Рауль; Уильямсон, Дрю; Дхаван, Эндрю; Скотт, Джейкоб (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

[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.

[HLP-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.