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

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

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

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

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

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

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

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

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

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

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

  • Известно, что определение того, является ли узел тривиальным, относится к классу сложности НП [11]
  • Как известно, задача определения рода узла имеет класс сложности PSPACE.
  • Существуют алгоритмы с полиномиальным временем для вычисления Полином александра узла.[12]

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

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

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

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

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

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

  1. ^ Афра Дж. Зомородян, Топология для вычислений, Кембридж, 2005, xi
  2. ^ Блевинс, Энн Сайзмор; Бассетт, Даниэль С. (2020), Шрираман, Бхарат (ред.), «Топология в биологии», Справочник по математике искусств и наук, Cham: Springer International Publishing, стр. 1–23, Дои:10.1007/978-3-319-70658-0_87-1, ISBN  978-3-319-70658-0
  3. ^ Б. ~ Бертон. Представляем Regina, программу для топологии 3-многообразий, Experimental Mathematics 13 (2004), 267–272.
  4. ^ http://www.warwick.ac.uk/~masgar/Maths/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». Adv. Математика. 256: 493–506. arXiv:1112.0845. Дои:10.1016 / j.aim.2014.01.007. S2CID  12634367.
  7. ^ Бертон, Бенджамин А .; Hyam Rubinstein, J .; Тилльманн, Стефан (2009). «Додекаэдрическое пространство Вебера-Зейферта не является Хакеном». arXiv:0909.4625. Цитировать журнал требует | журнал = (помощь)
  8. ^ Дж. Маннинг, Алгоритмическое обнаружение и описание гиперболических структур на трехмерных многообразиях с разрешимой проблемой слов, Геометрия и топология 6 (2002) 1–26
  9. ^ С. Матвеев, Алгоритмическая топология и классификация трехмерных многообразий, Springer-Verlag 2003
  10. ^ Костантино, Франческо; Терстон, Дилан (2008). «3-многообразия эффективно связывают 4-многообразия». Журнал топологии. 1 (3): 703–745. arXiv:математика / 0506577. Дои:10.1112 / jtopol / jtn017. S2CID  15119190.
  11. ^ Хасс, Джоэл; Лагариас, Джеффри С.; Пиппенгер, Николас (1999), "Вычислительная сложность задач узлов и зацеплений", Журнал ACM, 46 (2): 185–211, arXiv:математика / 9807016, Дои:10.1145/301970.301971, S2CID  125854.
  12. ^ "Главная страница ", Узел Атлас.
  13. ^ Анналы математики Э. Х. Брауна "Конечная вычислимость комплексов Постникова" (2) 65 (1957), стр. 1–20
  14. ^ Вадхва, Рауль; Уильямсон, Дрю; Дхаван, Эндрю; Скотт, Джейкоб (2018). «TDAstats: конвейер R для вычисления устойчивой гомологии при анализе топологических данных». Журнал открытого программного обеспечения. 3 (28): 860. Bibcode:2018JOSS .... 3..860R. Дои:10.21105 / joss.00860.

внешняя ссылка

Книги