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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

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